Browse Prior Art Database

ALGORITHMS FOR SOLVENTS OF MATRIX POLYNOMIALS

IP.com Disclosure Number: IPCOM000147913D
Original Publication Date: 1975-Oct-31
Included in the Prior Art Database: 2007-Mar-28

Publishing Venue

Software Patent Institute

Related People

Dennis Jr., J.E.: AUTHOR [+4]

Abstract

ALGORITHMS FOR SOLVENTS OF MATRIX POLYNOMIALS J. E. Dennis, Jr. Cornell University J. F. Traub Carnegie-Mellon University R. P. Weber B e l l Laboratories October, 1975 J. E. Dennis, Jr. was supported in part by National Science Foundation Grant GJ27528. J. F. Traub was supported in part by the National Science Foundation under Grant GJ32111 and the Office of Naval Research under Contract N0014-67-A-0314-0010, NR 044-422. 1. INTRODUCTION Let ,A,, X are n by n complex matrices. We call M(X) a monic matrix polvnomial of degree m. A matrix S for which M(S) Q is called a right solvent (or briefly a solvent), In Dennis, Traub, and Weber [76] we studied the algebraic theory of matrix polynomials. In this paper we analyze two algorithms for calculating a "dominant" solvent. (Dominant solvent is a generalization oflargest zero of a scalar polynomial. See Definition 2.1.) Algorithm 1 of this paper is a generalization of an algorithm for scalar polynomials (Traub [66]). It is globally convergent i n the following sense. If Stage One is done sufficiently long and if the hypotheses of Theorem 2.1 hold, then the iteration of Stage Two is globally convergent. Stage One may be viewed as direct powering by a "block companion matrix1'. We have not suc- ceeded in devising an inverse powering process as used by Jenkins and Traub [70]. Algorithm 2 is a generalization of Bernoulli's algorithm. A s in the scalar case, Bernoulli iteration may coilverge very slowly.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 24

ALGORITHMS FOR SOLVENTS OF MATRIX POLYNOMIALS
J. E. Dennis, Jr. Cornell University
J.
F. Traub

Carnegie-Mellon University
R. P. Weber

B e l l Laboratories

October, 1975

J. E. Dennis, Jr. was supported in part by National Science Foundation Grant GJ27528. J. F. Traub was supported in part by the National Science Foundation under Grant GJ32111 and the Office of Naval Research under Contract N0014-67-A-0314-0010, NR 044-422.

[This page contains 1 picture or other non-text object]

Page 2 of 24

[This page contains 1 picture or other non-text object]

Page 3 of 24

1. INTRODUCTION

Let

          ,A,, X are n by n complex matrices. We call M(X) a monic matrix polvnomial of degree m. A matrix S for which M(S) = -

                                     Q is called a right solvent (or briefly a solvent), In Dennis, Traub, and Weber [76] we studied the algebraic theory of matrix polynomials. In this paper we analyze two algorithms for calculating a "dominant" solvent. (Dominant solvent is a generalization of
largest zero of a scalar polynomial. See Definition 2.1.)

    Algorithm 1 of this paper is a generalization of an algorithm for scalar polynomials (Traub [66]). It is globally convergent i n the following sense. If Stage One is done sufficiently long and if the hypotheses of Theorem 2.1 hold, then the iteration of Stage Two is globally convergent. Stage One may be viewed as direct powering by a "block companion matrix1'. We have not suc- ceeded in devising an inverse powering process as used by Jenkins and Traub
[70]. Algorithm 2 is a generalization of Bernoulli's algorithm. A s in the scalar case, Bernoulli iteration may coilverge very slowly.

    In Dennis, Traub, and Weber [71] the relation between "block eigenvalue" and solvent is explored and two algorithms for the calculation of "block eigenvectors" are given. We do not pursue t:his here.

    M(X1) is called a lambda-matrix and a scalar X such that M(X1) is singular is called a latent root. An application of solvents i s to the calculation of latent roots,, If a l l the latent roots are distinct, and if the hypotheses of Theorem 2.1 are satisfied, then the dominant solvent may be computed. The dominant solvent may be removed and Algorithm 1 or 2 applied to the deflated

             m- 1 M(X)=xm+AIX + . . . + A m

where A, , . . .

[This page contains 1 picture or other non-text object]

Page 4 of 24

polynomial. The process can be repeated until a l l the latent roots have been computed. Other proposed methods for the calculation of latent roots such as algorithms of Lancaster [64] and Kublanovskaya ,[70] are only locally convergent and do not have an associated method of deflation. See Dennis, Traub, and Weber [71, Appendix B] for additional material on algorithms for lambda-matrices

    In Dennis, Traub, and Weber 1711 we give two globally convergent algor- ithms for calculating dominant latent roots. These results and their exten- sions will b...