Parametrization of Newton's iteration for computations with structured matrices and applications (Q1205895): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Pan, Victor Y. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Adrian Swift / rank | |||
Normal rank |
Revision as of 22:48, 9 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parametrization of Newton's iteration for computations with structured matrices and applications |
scientific article |
Statements
Parametrization of Newton's iteration for computations with structured matrices and applications (English)
0 references
1 April 1993
0 references
It is well known that the inversion of Toeplitz-like matrices can be performed in \(O(n \log^ 2n)\) operations. This paper commences with a summary of the performance of various related algorithms, expressed in terms of Brent's scheduling principle [cf. \textit{R. Karp}, \textit{V. Ramachandran}, Handbook of Theoretical Computer Science, 869-941, N-H, Amsterdam (1990)] for parallel processing, with complexity measure \(O_ A(t,p)\) giving simultaneous bounds on parallel arithmetic time \((t)\) and number of processors \((p)\). The previous best results were \(O_ A(n,\log^ 2n)\), with time complexity too high, or \(O_ A(\log^ 2n,n^{w+1})\), where \(w\) is such that the best result for multiplying \(n\times n\) matrices is \(O(n^ w)\). Then the author presents details of Toeplitz matrix computations over a field of constants \(F\) which allows division by \((n!)\). In this the coefficients of the characteristic polynomial of \(B\) are computed; this computation in turn reduces to computation of the traces of matrix powers of \(B\). These powers of \(B\) are computed using the Newton iteration for inversion of \(I-\lambda B\), for the scalar parameter \(\lambda\). Significantly improved complexity bounds are found. Subsequent sections extend the results to any field and discuss relevance to further computations with polynomials and general matrices. Finally, two appendices review relevant techniques with Toeplitz-like matrices and an expression for a least squares solution of a linear system.
0 references
performance
0 references
algorithms
0 references
parallel processing
0 references
complexity
0 references
Toeplitz matrix
0 references
Newton iteration
0 references
least squares solution
0 references