TR-2002015: Residual Correction Algorithms for General and Structured Matrices
Victor Ya. Pan, M. Kunin, Rhys Eric Rosholt, H. Cebecioglu · CUNY Academic Works (City University of New York) · 2002
We present and analyze residual correction algorithms for the computation of the inverses, generalized inverses, and numerical generalized inverses of general and structured matrices.For structured matrices, we extend the known algorithms by new policies of compression delay.For both structured and unstructured matrices, we propose and analyze the homotopic (continuation) methods, which supply close initial approximations.For unstructured indefinite 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 tests with Toeplitz input matrices show a greater power of both homotopic and non-homotopic approaches than the theoretical study predicts.