A unitary Hessenberg QR-based algorithm via semiseparable matrices

In this paper, we present a novel method for solving the unitary Hessenberg eigenvalue problem. In the first phase, an algorithm is designed to transform the unitary matrix into a diagonal-plus-semiseparable form. Then we rely on our earlier adaptation of the QR algorithm to solve the dpss eigenvalue problem in a fast and robust way. Exploiting the structure of the problem enables us to yield a quadratic time using a linear memory space. Nonetheless the algorithm remains robust and converges as fast as the customary QR algorithm. Numerical experiments confirm the effectiveness and the robustness of our approach.     

广义特征值极小扰动问题的一类黎曼共轭梯度法

研究含参数$l$非方矩阵对广义特征值极小扰动问题所导出的一类复乘积流形约束矩阵最小二乘问题.与已有工作不同,本文直接针对复问题模型,结合复乘积流形的几何性质和欧式空间上的改进Fletcher-Reeves共轭梯度法,设计一类适用于问题模型的黎曼非线性共轭梯度求解算法,并给出全局收敛性分析.数值实验和数值比较表明该算法比参数$l=1$的已有算法收敛速度更快,与参数$l=n$的已有算法能得到相同精度的解.与部分其它流形优化相比与已有的黎曼Dai非线性共轭梯度法具有相当的迭代效率,与黎曼二阶算法相比单步迭代成本较低、总体迭代时间较少,与部分非流形优化算法相比在迭代效率上有明显优势.     

On the Computation of Particular Eigenvectors of Hamiltonian Matrix Pencils

We discuss a structure-preserving algorithm for the accurate solution of generalized eigenvalue problems for skew-Hamiltonian/Hamiltonian matrix pencils λN − ℋ. By embedding the matrix pencil λ𝒩 − ℋ into a skew-Hamiltonian/Hamiltonian matrix pencil of double size it is possible to avoid the problem of non-existence of a structured Schur form. For these embedded matrix pencils we can compute a particular condensed form to accurately compute the simple, finite, purely imaginary eigenvalues of λ𝒩 − ℋ. In this paper we describe a new method to compute also the corresponding eigenvectors by using the information contained in the condensed form of the embedded matrix pencils and associated transformation matrices. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Numerical methods for palindromic eigenvalue problems: Computing the anti‐triangular Schur form

We present structure‐preserving numerical methods for the eigenvalue problem of complex palindromic pencils. Such problems arise in control theory, as well as from palindromic linearizations of higher degree palindromic matrix polynomials. A key ingredient of these methods is the development of an appropriate condensed form—the anti‐triangular Schur form. Ill‐conditioned problems with eigenvalues near the unit circle, in particular near ±1, are discussed. We show how a combination of unstructured methods followed by a structured refinement can be used to solve such problems accurately. Copyright © 2008 John Wiley & Sons, Ltd.     

An Approach to Solving Inverse Eigenvalue Problems for Matrices

The paper considers different formulations of inverse eigenvalue problems for matrices whose entries either polynomially or rationally depend on unknown parameters. An approach to solving inverse problems together with numerical algorithms is suggested. The solution of inverse problems is reduced to the problem of finding the so-called discrete solutions of nonlinear algebraic systems. The corresponding systems are constructed using the method of traces, and their discrete roots are found by applying the algorithms for solving nonlinear algebraic systems in several variables previously suggested by the author. Bibliography: 30 titles.     

The Schur algorithm and its applications

The Schur algorithm and its time-domain counterpart, the fast Cholseky recursions, are some efficient signal processing algorithms which are well adapted to the study of inverse scattering problems. These algorithms use a layer stripping approach to reconstruct a lossless scattering medium described by symmetric two-component wave equations which model the interaction of right and left propagating waves. In this paper, the Schur and fast Chokesky recursions are presented and are used to study several inverse problems such as the reconstruction of nonuniform lossless transmission lines, the inverse problem for a layered acoustic medium, and the linear least-squares estimation of stationary stochastic processes. The inverse scattering problem for asymmetric two-component wave equations corresponding to lossy media is also examined and solved by using two coupled sets of Schur recursions. This procedure is then applied to the inverse problem for lossy transmission lines.The work of this author was supported by the Exxon Education FoundationThe work of this author was supported by the Air Force Office of Scientific Research under Grant AFOSR-82-0135A.     

Implicit QR algorithms for palindromic and even eigenvalue problems

In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed. This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version. Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence. We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques. D. S. Watkins partly supported by Deutsche Forschungsgemeinschaft through Matheon, the DFG Research Center Mathematics for key technologies in Berlin.     

Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation

We study inexact subspace iteration for solving generalized non-Hermitian eigenvalue problems with spectral transformation, with focus on a few strategies that help accelerate preconditioned iterative solution of the linear systems of equations arising in this context. We provide new insights into a special type of preconditioner with “tuning” that has been studied for this algorithm applied to standard eigenvalue problems. Specifically, we propose an alternative way to use the tuned preconditioner to achieve similar performance for generalized problems, and we show that these performance improvements can also be obtained by solving an inexpensive least squares problem. In addition, we show that the cost of iterative solution of the linear systems can be further reduced by using deflation of converged Schur vectors, special starting vectors constructed from previously solved linear systems, and iterative linear solvers with subspace recycling. The effectiveness of these techniques is demonstrated by numerical experiments.     

Solving the eigenvalue problem for matrices

One presents some algorithms related among themselves for solving the partial and the complete eigenvalue problem for an arbitrary matrix. Algorithm 1 allows us to construct the invariant subspaces and to obtain with their aid a matrix whose eigenvalues coincide with the eigenvalues of the initial matrix and belong to a given semiplane. Algorithm 2 solves the same problem for a given strip. The algorithms 3 and 4 reduces the complete eigenvalue problem of an arbitrary matrix to some problem for a quasitriangular matrix whose diagonal blocks have eigenvalues with identical real parts. Algorithm 4 finds also the unitary matrix which realizes this transformation. One gives Algol programs which realize the algorithms 1–3 for real matrices and testing examples.     

On the quadratic two-parameter eigenvalue problem and its linearization

We introduce the quadratic two-parameter eigenvalue problem and linearize it as a singular two-parameter eigenvalue problem. This, together with an example from model updating, shows the need for numerical methods for singular two-parameter eigenvalue problems and for a better understanding of such problems.There are various numerical methods for two-parameter eigenvalue problems, but only few for nonsingular ones. We present a method that can be applied to singular two-parameter eigenvalue problems including the linearization of the quadratic two-parameter eigenvalue problem. It is based on the staircase algorithm for the extraction of the common regular part of two singular matrix pencils.     

Rational Krylov sequence methods for eigenvalue computation

Algorithms to solve large sparse eigenvalue problems are considered. A new class of algorithms which is based on rational functions of the matrix is described. The Lanczos method, the Arnoldi method, the spectral transformation Lanczos method, and Rayleigh quotient iteration all are special cases, but there are also new algorithms which correspond to rational functions with several poles. In the simplest case a basis of a rational Krylov subspace is found in which the matrix eigenvalue problem is formulated as a linear matrix pencil with a pair of Hessenberg matrices.     

Inverse spectral problems for differential pencils with boundary conditions dependent on the spectral parameter

In this paper, we discuss two inverse problems for differential pencils with boundary conditions dependent on the spectral parameter. We will prove the Hochstadt–Lieberman type theorem of 1 – 3 except for arbitrary one eigenvalue and the Borg type theorem of 1 – 3 except for at most arbitrary two eigenvalues, respectively. The new results are generalizations of the related results. Copyright © 2016 John Wiley & Sons, Ltd.     

A NOTE ON THE BACKWARD ERRORS FOR INVERSE EIGENVALUE PROBLEMS

In this note,we consider the backward errors for more general inverse eigenvalus prob-lems by extending Sun‘‘‘‘s approach.The optimal backward errors defined for diagonal-ization matrix inverse eigenvalue problem with respect to an approximate solution,and the upper and lower bounds are derived for the optimal backward errors.The results may be useful for testing the stability of practical algorithms.     

On the spectral properties of an operator pencil

For a broad class of iterative algorithms for solving saddle point problems, the study of the convergence and of the optimal properties can be reduced to an analysis of the eigenvalues of operator pencils of a special form. A new approach to analyzing spectral properties of pencils of this kind is proposed that makes it possible to obtain sharp estimates for the convergence rate.     

Principal minors, Part II: The principal minor assignment problem

The inverse problem of finding a matrix with prescribed principal minors is considered. A condition that implies a constructive algorithm for solving this problem will always succeed is presented. The algorithm is based on reconstructing matrices from their principal submatrices and Schur complements in a recursive manner. Consequences regarding the overdeterminancy of this inverse problem are examined, leading to a faster (polynomial time) version of the algorithmic construction. Care is given in the MATLAB^® implementation of the algorithms regarding numerical stability and accuracy.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems

Summary. We present generalizations of the nonsymmetric Levinson and Schur algorithms for non-Hermitian Toeplitz matrices with some singular or ill-conditioned leading principal submatrices. The underlying recurrences allow us to go from any pair of successive well-conditioned leading principal submatrices to any such pair of larger order. If the look-ahead step size between these pairs is bounded, our generalized Levinson and Schur recurrences require $ operations, and the Schur recurrences can be combined with recursive doubling so that an $ algorithm results. The overhead (in operations and storage) of look-ahead steps is very small. There are various options for applying these algorithms to solving linear systems with Toeplitz matrix. Received July 26, 1993     

二维抛物型方程参数反演的遗传算法

本文研究了二维抛物型方程参数反演问题.利用遗传算法求解此反演问题的方法,把参数反演问题转化为优化问题,通过演化计算方法求解.它从多个初始点开始寻优,借助交叉和变异算子来获得参数的全局最优解.且数值模拟结果表明,具有精度高、编程简单、易于计算机实现等特点.     

ARNOLDI TYPE ALGORITHMS FOR LARGE UNSYMMETRIC MULTIPLE EIGENVALUE PROBLEMS

1.IntroductionTheLanczosalgorithm[Zo]isaverypowerfultoolforextractingafewextremeeigenvaluesandassociatedeigenvectorsoflargesymmetricmatrices[4'5'22].Sincethe1980's,considerableattentionhasbeenpaidtogeneralizingittolargeunsymmetricproblems.Oneofitsgen...