Newton’s iteration for matrix inversion, advances and extensions. (English)
Olshevsky, Vadim (ed.) et al., Matrix methods. Theory, algorithms and applications. Dedicated to the memory of Gene Golub. Based on the 2nd international conference on matrix methods and operator equations, Moscow, Russia, July 23‒27, 2007. Hackensack, NJ: World Scientific (ISBN 978-981-283-601-4/hbk). 364-381 (2010).
Summary: We first cover Newton’s iteration for generalized matrix inversion, its ameliorations, recursive compression of its iterates in the case of structured inputs, some techniques of continuation via factorization, and extension to splitting the singular value decomposition. We combine the latter extension with our recent fast algorithms for the null space bases (prompted by our progress in randomized preconditioning). We apply these combinations to compute the respective spaces of singular vectors and to arrive at divide-and-conquer algorithms for matrix inversion and computing determinants. Our techniques promise to be effective for computing other matrix functions in the case of ill conditioned inputs.