Newton's iteration for structured matrices.
详细信息
- 作者：Rosholt ; Rhys Eric.
- 学历：Doctor
- 年：2003
- 导师：Pan, Victor
- 毕业院校：City University of New York
- 专业：Computer Science.
- CBH：3083704
- Country：USA
- 语种：English
- FileSize：3527299
- Pages：114
文摘
In the first part of the thesis (Chapters 1–5), we study four quadratically convergent algorithms for the refinement of rough initial approximations to the inverses of n x n non-singular Toeplitz and Toeplitz-like matrices and to the solutions of non-singular Toeplitz and Toeplitz-like linear systems of n equations. The algorithms are variations of Newton's iteration, adjusted to structured matrix computations based on the known inversion formulas for Toeplitz matrices and the displacement representations of Toeplitz-like matrices. Due to using matrix structure, each iteration step is performed in O(n log n) time. The algorithms can be extended to the case of structured matrices of other classes.;In the second part of the thesis (Chapters 6–11), we study more general residual correction algorithms for the computation of the inverses of general and structured matrices. For structured matrices, we extend the algorithms by new policies of compression delay. For both structured and unstructured matrices, we study the homotopic (continuation) methods, which supply close initial approximations. For unstructured indefinite complex Hermitian input matrices, the homotopy methods enable substantial acceleration of the known best non-homotopic algorithms. Furthermore, by using homotopic techniques, we guarantee superlinear convergence to the inverses of structured matrices even where no initial approximation is available and where compression of displacement generators is ensured in every residual correction step.;Numerical experiments on the initial four algorithms confirm the results of our analysis and the efficiency of the algorithms. Numerical tests with Toeplitz input matrices show a greater power of both homotopic and non-homotopic approaches than the theoretical study predicts.