Parametrization of Newton's iteration for computations with structured matrices and applications (Q1205895)

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.