| Recent progress in the study of structured matrices shows advantages of unifying the treatment of various classes of such matrices. We show such a unified treatment of Newton's iteration which rapidly improves an initial approximation to matrix inverse by performing two matrix multiplications per recursive step. The iteration is particularly suitable for the inversion of structured matrices because in this case matrix operations are performed much more rapidly and with O(no) entries of short generators of structured matrices rather than with order of n 2 entries of the input matrix, that is, using much less memory space. A major problem is to control the length of the generator, which tends to grow quite rapidly in the iterative process. Some techniques of 1992--93 propose to control the growth in the Toeplitz-like case by relying on the concept of approximate orthogonal displacement rank, other techniques of 1997--99 used substitution of the computed approximations for the inverse matrix in the expression for the generators of Newton's iterates. We study both variant of the iteration for the more general class of structured matrices, propose some variations of the iterative process and of the techniques for controlling the length of the generators, and investigate the convergence rate as well as computational complexity. Some novel techniques are introduced in this study, in particular for the estimation of the norms of the auxiliary operators. We also summarize and unify the representation of structured matrices via their short generators. |
