Homotopic residual correction processes
Authors:
V. Y. Pan, M. Kunin, R. E. Rosholt and H. Kodal
Journal:
Math. Comp. 75 (2006), 345368
MSC (2000):
Primary 65F10, 65F30
Published electronically:
July 25, 2005
MathSciNet review:
2176403
Fulltext 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 preestimation of the smallest singular value of an input matrix. Furthermore, we guarantee rapid convergence to the inverses of wellconditioned structured matrices even where no good initial approximation is available. In particular we yield the inverse of a wellconditioned 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 wellconditioned 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
(87a:65073), http://dx.doi.org/10.1137/0906025
 [BI66]
A. BenIsrael, A Note on Iterative Method for Generalized Inversion of Matrices, Math. Comp., 20, 439440, 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
(2002g:15030), http://dx.doi.org/10.1090/conm/281/04659
 [CKLA87]
J.
Chun, T.
Kailath, and H.
LevAri, Fast parallel algorithms for 𝑄𝑅 and
triangular factorization, SIAM J. Sci. Statist. Comput.
8 (1987), no. 6, 899–913. MR 911062
(89e:65035), http://dx.doi.org/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 (2000f:15001), http://dx.doi.org/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
FranciscoLondon, 1963. MR 0158519
(28 #1742)
 [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
(90d:65055)
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
(97g:65006)
 [HH93]
Georg
Heinig and Frank
Hellinger, On the Bezoutian structure of the MoorePenrose inverses
of Hankel matrices, SIAM J. Matrix Anal. Appl. 14
(1993), no. 3, 629–645. MR 1227768
(94f:15006), http://dx.doi.org/10.1137/0614044
 [HH94]
Georg
Heinig and Frank
Hellinger, MoorePenrose inversion of square Toeplitz
matrices, SIAM J. Matrix Anal. Appl. 15 (1994),
no. 2, 418–450. MR 1266596
(95c:15008), http://dx.doi.org/10.1137/S0895479892225853
 [IK66]
Eugene
Isaacson and Herbert
Bishop Keller, Analysis of numerical methods, John Wiley &
Sons, Inc., New YorkLondonSydney, 1966. MR 0201039
(34 #924)
 [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
(80k:65029), http://dx.doi.org/10.1016/0022247X(79)901240
 [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
(2000h:65003)
 [P90]
Victor
Pan, On computations with dense structured
matrices, Math. Comp. 55
(1990), no. 191, 179–190. MR 1023051
(90m:65085), http://dx.doi.org/10.1090/S00255718199010230517
 [P92]
Victor
Pan, Parallel solution of Toeplitzlike linear systems, J.
Complexity 8 (1992), no. 1, 1–21. MR 1153611
(92k:65202), http://dx.doi.org/10.1016/0885064X(92)900316
 [P92b]
V. Y. Pan, Can We Utilize the Cancelation of the Most Significant Digits? Tech. Report TR92061, 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 (93k:15039), http://dx.doi.org/10.1137/0614010
 [P01a]
Victor
Y. Pan, Structured matrices and polynomials, Birkhäuser
Boston, Inc., Boston, MA; SpringerVerlag, New York, 2001. Unified
superfast algorithms. MR 1843842
(2002i:65001)
 [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, 644649, Springer, Berlin, 2001.
 [Pa]
V. Y. Pan, A Homotopic/Factorization Process for Toeplitzlike 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 AiLong
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), 7990, 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 (2002m:65036), http://dx.doi.org/10.1016/S00243795(01)003366
 [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
(92d:65056), http://dx.doi.org/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. 23, 581–592. MR 2073066
(2005g:65064), http://dx.doi.org/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
(2004a:47012), http://dx.doi.org/10.1137/S089547980238627X
 [PZHD97]
Victor
Y. Pan, Ailong
Zheng, Xiaohan
Huang, and Olen
Dias, Newton’s iteration for inversion of Cauchylike and
other structured matrices, J. Complexity 13 (1997),
no. 1, 108–124. MR 1449764
(98h:65014), http://dx.doi.org/10.1006/jcom.1997.0431
 [Par80]
B. N. Parlett, The Symmetric Eigenvalue Problem, PrenticeHall, Englewood Cliffs, NJ, 1980. MR (81j:65063)
 [S33]
G. Schultz, Iterative Berechnung der Reciproken Matrix, Z. Angew. Meth. Mech., 13, 5759, 1933.
 [SS74]
Torsten
Söderström and G.
W. Stewart, On the numerical properties of an iterative method for
computing the MoorePenrose generalized inverse, SIAM J. Numer. Anal.
11 (1974), 61–74. MR 0341843
(49 #6589)
 [B85]
 J. R. Bunch, Stability of Methods for Solving Toeplitz Systems of Equations, SIAM Journal on Scientific and Statistical Computing, 6, 2, 349364, 1985. MR 0779410 (87a:65073)
 [BI66]
 A. BenIsrael, A Note on Iterative Method for Generalized Inversion of Matrices, Math. Comp., 20, 439440, 1966.
 [BM01]
 D. A. Bini, B. Meini, Approximate displacement rank and applications, Structured Matrices in Mathematics, Computer Science, and Engineering II (V. Olshevsky Editor), Contemporary Mathematics, 281, 215232, American Mathematical Society, Rhode Island, 2001. MR 1855993 (2002g:15030)
 [CKLA87]
 J. Chun, T. Kailath, H. LevAri, Fast Parallel Algorithm for QRfactorization of Structured Matrices, SIAM Journal on Scientific and Statistical Computing, 8, 6, 899913, 1987. MR 0911062 (89e:65035)
 [EPY98]
 I. A. Emiris, V. Y. Pan, Y. Yu, Modular Arithmetic for Linear Algebra Computations in the Real Field, J. of Symbolic Computation, 26, 7187, 1998.MR 1633585 (2000f:15001)
 [FF63]
 D. K. Faddeev, V. N. Faddeeva, Computational Methods of Linear Algebra, W. H. Freeman, San Francisco, 1963. MR 0158519 (28:1742)
 [GL96]
 G. H. Golub, C. F. Van Loan, Matrix Computations, Johns Hopkins Univeristy Press, Baltimore, Maryland, 1989 (2nd edition), 1996 (3rd edition). MR 1002570 (90d:65055); MR 1417720 (97g:65006)
 [HH93]
 G. Heinig, F. Hellinger, On the Bezoutian Structure of the MoorePenrose Inverses of Hankel Matrices, SIAM J. on Matrix Analysis and Applications, 14, 3, 629645, 1993. MR 1227768 (94f:15006)
 [HH94]
 G. Heinig, F. Hellinger, MoorePenrose Generalized Inverse of Square Toeplitz Matrices, SIAM J. on Matrix Analysis and Applications, 15, 2, 418450, 1994. MR 1266596 (95c:15008)
 [IK66]
 E. Issacson, H. B. Keller, Analysis of Numerical Methods, Wiley, New York, 1966. MR 0201039 (34:924)
 [KKM79]
 T. Kailath, S. Y. Kung, M. Morf, Displacement Ranks of Matrices and Linear Equations, J. Math. Anal. Appl., 68, 2, 395407, 1979. MR 0533501 (80k:65029)
 [KS99]
 T. Kailath, A. H. Sayed (Editors), Fast Reliable Algorithms for Matrices with Structure, SIAM Publications, Philadelphia, 1999. MR 1715813 (2000h:65003)
 [P90]
 V. Y. Pan, On Computations with Dense Structured Matrices, Math. Comp., 55, 191, 179190, 1990. Proceeding version: Proc. Intern. Symp. on Symbolic and Algebraic Comp. (ISSAC'89), 3442, ACM Press, New York, 1989. MR 1023051 (90m:65085)
 [P92]
 V. Y. Pan, Parallel Solution of Toeplitzlike Linear Systems, J. of Complexity, 8, 121, 1992. MR 1153611 (92k:65202)
 [P92b]
 V. Y. Pan, Can We Utilize the Cancelation of the Most Significant Digits? Tech. Report TR92061, The International Computer Science Institute, Berkeley, California, 1992.
 [P93]
 V. Y. Pan, Decreasing the Displacement Rank of a Matrix, SIAM Journal on Matrix Analysis and Applications, 14, 1, 118121, 1993. MR 1199549 (93k:15039)
 [P01a]
 V. Y. Pan, Structured Matrices and Polynomials: Unified Superfast Algorithms, Birkhäuser/Springer, Boston/New York, 2001. MR 1843842 (2002i:65001)
 [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, 644649, Springer, Berlin, 2001.
 [Pa]
 V. Y. Pan, A Homotopic/Factorization Process for Toeplitzlike 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]
 V. Y. Pan, S. Branham, R. Rosholt, A. Zheng, Newton's Iteration for Structured Matrices and Linear Systems of Equations, SIAM volume on Fast Reliable Algorithms for Matrices with Structure, (T. Kailath, A.H. Sayed, Editors), 189210, SIAM Publications, Philadelphia, 1999. 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), 7990, Nova Science Publishers, Huntington, New York, 2001.
 [PRW02]
 V. Y. Pan, Y. Rami, X. Wang, Structured Matrices and Newton's Iteration: Unified Approach, Linear Algebra and Its Applications, 343344, 233265, 2002. MR 1878944 (2002m:65036)
 [PS91]
 V. Y. Pan, R. Schreiber, An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications, SIAM J. on Scientific and Statistical Computing, 12, 5, 11091131, 1991. MR 1114976 (92d:65056)
 [PVBWC04]
 V. Y. Pan, M. Van Barel, X. Wang, G. Codevico, Iterative Inversion of Structured Matrices, Theoretical Computer Science, 315, 23, 581592 (Special Issue on Algebraic and Numerical Computing), 2004.MR 2073066
 [PW03]
 V. Y. Pan and X. Wang, Inversion of Displacement Operators. SIAM Journal on Matrix Analysis and Applications, 24, 3, 660677, 2003. MR 1972673 (2004a:47012)
 [PZHD97]
 V. Y. Pan, A. Zheng, X. Huang, O. Dias, Newton's Iteration for Inversion of Cauchylike and Other Structured Matrices, J. of Complexity, 13, 108124, 1997. MR 1449764 (98h:65014)
 [Par80]
 B. N. Parlett, The Symmetric Eigenvalue Problem, PrenticeHall, Englewood Cliffs, NJ, 1980. MR (81j:65063)
 [S33]
 G. Schultz, Iterative Berechnung der Reciproken Matrix, Z. Angew. Meth. Mech., 13, 5759, 1933.
 [SS74]
 T. Söderström, W. Stewart, On the Numerical Properties of an Iterative Method for Computing the MoorePenrose Generalized Inverse, SIAM J. Numer. Anal., 11, 6174, 1974. MR 0341843 (49:6589)
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
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/S0025571805017710
PII:
S 00255718(05)017710
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 633830032 and 664060033, 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.
