Homotopic residual correction processes

Creative Commons License

Pan V., Kunin M., Rosholt R., Kodal H.

MATHEMATICS OF COMPUTATION, cilt.75, sa.253, ss.345-368, 2006 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 75 Sayı: 253
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1090/s0025-5718-05-01771-0
  • Dergi Adı: MATHEMATICS OF COMPUTATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.345-368
  • Anahtar Kelimeler: esidual correction, Newton's iteration, homotopic (continuation) algorithms, (generalized) inverse matrix, STRUCTURED MATRICES, NEWTONS ITERATION, GENERALIZED INVERSE, COMPUTATIONS, EQUATIONS
  • Kocaeli Üniversitesi Adresli: Evet

Özet

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 X n matrix with a structure of Toeplitz/Hankel type in O(n log(3) n) 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 de. ne our algorithms.