Newton-Structured Numerical Iteration

Victor Y. Pan
Additional contact information
Victor Y. Pan: Lehman College, CUNY, Department of Mathematics and Computer Science

Chapter Chapter 6 in Structured Matrices and Polynomials, 2001, pp 177-218 from Springer

Abstract: Abstract Newton’s iteration rapidly refines a crude initial approximation to the inverse or the Moore—Penrose generalized inverse of a structured matrix. The algorithm can be applied to a general matrix but is dramatically accelerated and becomes superfast where the well conditioned matrix is structured. Newton's iteration is strongly stable numerically and is reduced essentially to performing matrix multiplication twice per an iterative step. Multiplication is inexpensive, easy to implement on computers, and effectively parallelizable for structured matrices represented in compressed form, but the structure rapidly deteriorates in the process of the iteration. In this chapter we cover the following main subjects. a) We develop two general techniques for preserving both structure and superlinear convergence. One of the techniques is purely numerical, SVD based. It allows variation of the compression level, which enables a trade-off between the structure and the convergence rate or, equivalently, between the levels of compression and the approximation errors. Another technique can be applied over any field, although in this chapter we assume numerical application. b) For our two resulting versions of the Newton-Structured Iteration, we estimate their convergence rates and computational cost in flops. c) This analysis is ultimately reduced to estimating the norms of the inverse displacement operators, and we show five approaches to obtaining these estimates. d) We describe some policies for convergence acceleration and choosing an initial approximation to the inverse matrix. e) We describe homotopic processes with Newton's iteration as their basic subroutine (for general and structured matrices). The homotopic approach ensures superfast numerical inversion of well conditioned Toeplitz-like and other structured matrices, which can be implemented in polylogarithmic parallel arithmetic time on n processors. f) Non-homotopic versions of the Newton-Structured Iteration do not have theoretical support of their superfast performance, but this may partly be the result of the overly pessimistic nature of the available analysis techniques. Numerical experiments should ultimately determine the relative efficiency of the homotopic and non-homotopic approaches for practical computation and help optimize their variations, in particular in choosing appropriate policies for choosing the step sizes in the homotopic processes and for compression and scaling the iterates. We show the results of some experimental numerical computations with Toeplitz matrices. The study in this chapter brings the reader to some open problems in the ongoing research. More than in other chapters, the presentation omits proofs, derivations, and other technical details, which we replace by references to bibliography.

Keywords: Input Matrix; Toeplitz Matrice; Residual Norm; Newton Step; Compression Level (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-0129-8_6

Ordering information: This item can be ordered from
http://www.springer.com/9781461201298

DOI: 10.1007/978-1-4612-0129-8_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().