An algorithm for rescaling a matrix positive definite

For a given square real matrix M, we present a general algorithm which decides the existence of a positive diagonal matrix D such that DM is positive definite and which constructs the D if it exists. It is shown that solving this matrix rescaling problem is equivalent to finding a solution of an infinite system of linear inequalities. The algorithm solves this infinite system of linear inequalities by generating and solving a sequence of linear programs.     

Convergent matrix pencils

This paper deals with the study of sufficient conditions to guarantee that matrices expressed as a matrix pencil of a pair of given matrices be convergent.     

Preconditioning spectral element schemes for definite and indefinite problems

Spectral element schemes for the solution of elliptic boundary value problems are considered. Preconditioning methods based on finite difference and finite element schemes are implemented. Numerical experiments show that inverting the preconditioner by a single multigrid iteration is most efficient and that the finite difference preconditioner is superior to the finite element one for both definite and indefinite problems. A multigrid preconditioner is also derived from the finite difference preconditioner and is found suitable for the CGS acceleration method. It is pointed out that, for the finite difference and finite element preconditioners, CGS does not always converge to the accurate algebraic solution. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 535–543, 1999     

Implicit QR for rank-structured matrix pencils

A fast implicit QR algorithm for eigenvalue computation of low rank corrections of Hermitian matrices is adjusted to work with matrix pencils arising from zerofinding problems for polynomials expressed in Chebyshev-like bases. The modified QZ algorithm computes the generalized eigenvalues of certain $N\times N$ rank structured matrix pencils using $O(N^2)$ flops and $O(N)$ memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.     

Definitizable hermitian matrix pencils

Summary An hermitian matrix pencilA – B withA nonsingular is called strongly definitizable ifAp(A ^–1 B) is positive definite for some polynomialp. We present three characterizations of strongly definitizable pencils, which generalize the classical results for definite pencils. They are, in particular, stably simultaneously diagonable. We also discuss this form of stability with respect to an open subset of the real line. Implications for some quadratic eigenvalue problems are included.Research supported in part by the National Sciences and Engineering Research Council of Canada.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

Analysis of singular matrix pencils

One considers the spectral problem for a singular pencil D(λ)=A + λB of matrices A and B (A and B are rectangular matrices or det D(λ)≡0). One represents an algorithm which allows us to find the reducing subspaces for D(λ) and with their aid to reduce the dimension of the initial pencil, by isolating from it the zero block, the blocks corresponding to the right and left polynomial solutions of the equations (A+λB)x(λ)=0 and y(λ)(A+λB)=0, respectively, as well as the block corresponding to the regular kernel of the pencil D(λ). The algorithm is based on the application of the normalized process which uses the numerically stable elementary orthogonal transformations (the matrices of plane rotations or reflections).     

Rayleigh quotient algorithms for nonsymmetric matrix pencils

A classical Rayleigh-quotient iterative algorithm (known as “broken iteration”) for finding eigenvalues and eigenvectors is applied to semisimple regular matrix pencils A − λB. It is proved that cubic convergence is attained for eigenvalues and superlinear convergence of order three for eigenvectors. Also, each eigenvalue has a local basin of attraction. A closely related Newton algorithm is examined. Numerical examples are included. Dedicated to the memory of Gene H. Golub.     

A deflation method for regular matrix pencils

A generalization of the concept of eigenvalue is introduced for a matrix pencil and it is called eigenpencil; an eigenpencil is a pencil itself and it contains part of the spectral information of the matrix pencil. A Wielandt type deflation procedure for regular matrix pencils is developed, using eigenpencils and supposing that they can have both finite and infinite eigenvalues. A numerical example illustrates the proposed method.     

Pseudospectra for matrix pencils and stability of equilibria

The concept of ε-pseudospectra for matrices, introduced by Trefethen and his coworkers, has been studied extensively since 1990. In this paper, ε-pseudospectra for matrix pencils, which are relevant in connection with generalized eigenvalue problems, are considered. Some properties as well as the practical computation of ε-pseudospectra for matrix pencils will be discussed. As an application, we demonstrate how this concept can be used for investigating the asymptotic stability of stationary solutions to time-dependent ordinary or partial differential equations; two cases, based on Burgers' equation, will be shown. This research has been supported by the Netherlands Organization for Scientific Research (N.W.O.)     

Canonical forms for mixed symmetric-skewsymmetric quaternion matrix pencils

Canonical forms are described for pairs of quaternionic matrices, or equivalently matrix pencils, where one matrix is symmetric and the other matrix is skewsymmetric, under strict equivalence and symmetry respecting congruence. The symmetry is understood in the sense of a fixed involutory antiautomorphism of the skew field of the real quaternions; the involutory antiautomorphism is assumed to be nonstandard, i.e., other than the quaternionic conjugation. Some applications are developed, such as canonical forms for quaternionic matrices under symmetry respecting congruence, and canonical forms for matrices that are skewsymmetric with respect to a nondegenerate symmetric or skewsymmetric quaternion valued inner product.     

Spectral problem for polynomial matrix pencils. 2

For an arbitrary polynomial pencil of matrices A_i of dimensions m×n one presents an algorithm for the computation of the eigenvalues of the regular kernel of the pencil. The algorithm allows to construct a regular pencil having the same eigenvalues as the regular kernel of the initial pencil or (in the case of a dead end termination) allows to pass from the initial pencil to a pencil of smaller dimensions whose regular kernel has the same eigenvalues as the initial pencil. The problem is solved by reducing the obtained pencil to a linear one. For solving the problem in the case of a linear pencil one considers algorithms for pencils of full column rank as well as for completely singular pencils.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 109–116, 1981.     

Compact perturbation of definite type spectra of self-adjoint quadratic operator pencils

Self-adjoint quadratic operator pencilsL()= ² A + B + C with a noninvertible leading operatorA are considered. In particular, a characterization of the spectral points of positive and of negative type ofL is given, and their behavior under a compact perturbation is studied. These results are applied to a pencil arising in magnetohydrodynamics.     

Methods for solving spectral problems for multiparameter matrix pencils

Methods for solving the partial eigenproblem for multiparameter regular pencils of real matrices, which allow one to improve given approximations of an eigenvector and the associated point of the spectrum (both finite and infinite) are suggested. Ways of extending the methods to complex matrices, polynomial matrices, and coupled multiparameter problems are indicated. Bibliography: 10 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 296, 2003, pp. 139–168.     

Identities for sums of characteristic values of entire matrix pencils

The paper deals with an entire matrix-valued function of a complex argument (an entire matrix pencil) f of order ρ(f)<∞. Identities for the following sums of the characteristic values of f are established: