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 Free Access

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 matrix with a structure of Toeplitz/Hankel type in 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.

**[B85]**James R. Bunch,*Stability of methods for solving Toeplitz systems of equations*, SIAM J. Sci. Statist. Comput.**6**(1985), no. 2, 349–364. MR**779410**, 10.1137/0906025**[B-I66]**A. Ben-Israel, A Note on Iterative Method for Generalized Inversion of Matrices,*Math. Comp.*,**20**, 439-440, 1966.**[BM01]**Dario Andrea Bini and Beatrice Meini,*Approximate displacement rank and applications*, Structured matrices in mathematics, computer science, and engineering, II (Boulder, CO, 1999) Contemp. Math., vol. 281, Amer. Math. Soc., Providence, RI, 2001, pp. 215–232. MR**1855993**, 10.1090/conm/281/04659**[CKL-A87]**J. Chun, T. Kailath, and H. Lev-Ari,*Fast parallel algorithms for 𝑄𝑅 and triangular factorization*, SIAM J. Sci. Statist. Comput.**8**(1987), no. 6, 899–913. MR**911062**, 10.1137/0908073**[EPY98]**Ioannis Z. Emiris, Victor Y. Pan, and Yanqiang Yu,*Modular arithmetic for linear algebra computations in the real field*, J. Symbolic Comput.**26**(1998), no. 1, 71–87. MR**1633585**, 10.1006/jsco.1998.0201**[FF63]**D. K. Faddeev and V. N. Faddeeva,*Computational methods of linear algebra*, Translated by Robert C. Williams, W. H. Freeman and Co., San Francisco-London, 1963. MR**0158519****[GL96]**Gene H. Golub and Charles F. Van Loan,*Matrix computations*, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR**1002570**

Gene H. Golub and Charles F. Van Loan,*Matrix computations*, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR**1417720****[HH93]**Georg Heinig and Frank Hellinger,*On the Bezoutian structure of the Moore-Penrose inverses of Hankel matrices*, SIAM J. Matrix Anal. Appl.**14**(1993), no. 3, 629–645. MR**1227768**, 10.1137/0614044**[HH94]**Georg Heinig and Frank Hellinger,*Moore-Penrose inversion of square Toeplitz matrices*, SIAM J. Matrix Anal. Appl.**15**(1994), no. 2, 418–450. MR**1266596**, 10.1137/S0895479892225853**[IK66]**Eugene Isaacson and Herbert Bishop Keller,*Analysis of numerical methods*, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR**0201039****[KKM79]**Thomas Kailath, Sun Yuan Kung, and Martin Morf,*Displacement ranks of matrices and linear equations*, J. Math. Anal. Appl.**68**(1979), no. 2, 395–407. MR**533501**, 10.1016/0022-247X(79)90124-0**[KS99]**T. Kailath and A. H. Sayed (eds.),*Fast reliable algorithms for matrices with structure*, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. MR**1715813****[P90]**Victor Pan,*On computations with dense structured matrices*, Math. Comp.**55**(1990), no. 191, 179–190. MR**1023051**, 10.1090/S0025-5718-1990-1023051-7**[P92]**Victor Pan,*Parallel solution of Toeplitzlike linear systems*, J. Complexity**8**(1992), no. 1, 1–21. MR**1153611**, 10.1016/0885-064X(92)90031-6**[P92b]**V. Y. Pan,*Can We Utilize the Cancelation of the Most Significant Digits? Tech. Report TR-92-061*, The International Computer Science Institute, Berkeley, California, 1992.**[P93]**Victor Pan,*Decreasing the displacement rank of a matrix*, SIAM J. Matrix Anal. Appl.**14**(1993), no. 1, 118–121. MR**1199549**, 10.1137/0614010**[P01a]**Victor Y. Pan,*Structured matrices and polynomials*, Birkhäuser Boston, Inc., Boston, MA; Springer-Verlag, New York, 2001. Unified superfast algorithms. MR**1843842****[P01b]**V. Y. Pan, A Homotopic Residual Correction Process,*Proceedings of the Second Conference on Numerical Analysis and Applications*(P. Yalamov, editor),*Lecture Notes in Computer Science*,**1988**, 644-649, Springer, Berlin, 2001.**[Pa]**V. Y. Pan, A Homotopic/Factorization Process for Toeplitz-like Matrices with Newton's/Conjugate Gradient Stages, Technical Report TR 2004014,*Ph.D. Program in Computer Science, Graduate Center, City University of New York*, New York, 2004.**[PBRZ99]**Victor Y. Pan, Sheryl Branham, Rhys E. Rosholt, and Ai-Long Zheng,*Newton’s iteration for structured matrices*, Fast reliable algorithms for matrices with structure, SIAM, Philadelphia, PA, 1999, pp. 189–210. MR**1715820****[PKRC02]**V. Y. Pan, M. Kunin, R. Rosholt, H. Cebecioglu, Residual Correction Algorithms for General and Structured Matrices, Technical Report TR 2002020,*Ph.D. Program in Computer Science, Graduate Center, City University of New York*, New York, 2002.**[PMRTY]**V. Y. Pan, B. Murphy, R. E. Rosholt, Y. Tang, X. Yan, Additive Preconditioning in Matrix Computations, Technical Report TR 2005009,*Ph.D. Program in Computer Science, Graduate Center, City University of New York*, New York, 2005.**[PR01]**V. Y. Pan, Y. Rami, Newton's Iteration for the Inversion of Structured Matrices,*Advances in the Theory of Computational Mathematics, Vol. 4: Structured Matrices: Recent Developments in Theory and Computation*, (edited by D. A. Bini, E. Tyrtyshnikov and P. Yalamov), 79-90, Nova Science Publishers, Huntington, New York, 2001.**[PRW02]**Victor Y. Pan, Youssef Rami, and Xinmao Wang,*Structured matrices and Newton’s iteration: unified approach*, Linear Algebra Appl.**343/344**(2002), 233–265. Special issue on structured and infinite systems of linear equations. MR**1878944**, 10.1016/S0024-3795(01)00336-6**[PS91]**Victor Pan and Robert Schreiber,*An improved Newton iteration for the generalized inverse of a matrix, with applications*, SIAM J. Sci. Statist. Comput.**12**(1991), no. 5, 1109–1130. MR**1114976**, 10.1137/0912058**[PVBWC04]**Victor Y. Pan, Marc Van Barel, Xinmao Wang, and Gianni Codevico,*Iterative inversion of structured matrices*, Theoret. Comput. Sci.**315**(2004), no. 2-3, 581–592. MR**2073066**, 10.1016/j.tcs.2004.01.008**[PW03]**Victor Y. Pan and Xinmao Wang,*Inversion of displacement operators*, SIAM J. Matrix Anal. Appl.**24**(2003), no. 3, 660–677. MR**1972673**, 10.1137/S089547980238627X**[PZHD97]**Victor Y. Pan, Ailong Zheng, Xiaohan Huang, and Olen Dias,*Newton’s iteration for inversion of Cauchy-like and other structured matrices*, J. Complexity**13**(1997), no. 1, 108–124. MR**1449764**, 10.1006/jcom.1997.0431**[Par80]**B. N. Parlett,*The Symmetric Eigenvalue Problem*, Prentice-Hall, Englewood Cliffs, NJ, 1980. MR**(81j:65063)****[S33]**G. Schultz, Iterative Berechnung der Reciproken Matrix,*Z. Angew. Meth. Mech.*,**13**, 57-59, 1933.**[SS74]**Torsten Söderström and G. W. Stewart,*On the numerical properties of an iterative method for computing the Moore-Penrose generalized inverse*, SIAM J. Numer. Anal.**11**(1974), 61–74. MR**0341843**

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

Email:
victor.pan@lehman.cuny.edu

**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

DOI:
http://dx.doi.org/10.1090/S0025-5718-05-01771-0

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.