Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Homotopic residual correction processes

Authors: V. Y. Pan, M. Kunin, R. E. Rosholt and H. Kodal
Journal: Math. Comp. 75 (2006), 345-368
MSC (2000): Primary 65F10, 65F30
Published electronically: July 25, 2005
MathSciNet review: 2176403
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present and analyze homotopic (continuation) residual correction algorithms for the computation of matrix inverses. For complex indefinite Hermitian input matrices, our homotopic methods substantially accelerate the known nonhomotopic algorithms. Unlike the nonhomotopic case our algorithms require no pre-estimation of the smallest singular value of an input matrix. Furthermore, we guarantee rapid convergence to the inverses of well-conditioned structured matrices even where no good initial approximation is available. In particular we yield the inverse of a well-conditioned $n \times n$ matrix with a structure of Toeplitz/Hankel type in $O(n\log^3n)$ flops. For a large class of input matrices, our methods can be extended to computing numerically the generalized inverses. Our numerical experiments confirm the validity of our analysis and the efficiency of the presented algorithms for well-conditioned input matrices and furnished us with the proper values of the parameters that define our algorithms.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F10, 65F30

Retrieve articles in all journals with MSC (2000): 65F10, 65F30

Additional Information

V. Y. Pan
Affiliation: Mathematics and Computer Science Department, Lehman College, CUNY, Bronx, New York 10468; Ph. D. Program in Mathematics, Graduate Center, CUNY, New York, New York 10016

M. Kunin
Affiliation: Ph.D. Program in Computer Science, Graduate Center, CUNY, New York, New York 10016

R. E. Rosholt
Affiliation: Mathematics and Computer Science Department, Lehman College, CUNY, Bronx, New York 10468

H. Kodal
Affiliation: University of Kocaeli, Department of Mathematics, 41300 Izmit, Kocaeli, Turkey

Keywords: Residual correction, Newton's iteration, homotopic (continuation) algorithms, (generalized) inverse matrix
Received by editor(s): December 20, 2001
Received by editor(s) in revised form: March 10, 2004
Published electronically: July 25, 2005
Additional Notes: This work was supported by NSF Grant CCR9732206, PSC CUNY Awards 63383-0032 and 66406-0033, and a Grant from the CUNY Institute for Software Design and Development (CISDD)
The results of this paper were presented at the Second Conference on Numerical Analysis and Applications, Rousse, Bulgaria, in June 2000, and at the AMS/IMS/SIAM Summer Research Conference on Fast Algorithms in Mathematics, Computer Science, and Engineering in South Hadley, Massachusetts, in August 2001.
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society