Continuous methods for extreme and interior eigenvalue problems

In this paper, continuous methods are introduced to compute both the extreme and interior eigenvalues and their corresponding eigenvectors for real symmetric matrices. The main idea is to convert the extreme and interior eigenvalue problems into some optimization problems. Then a continuous method which includes both a merit function and an ordinary differential equation (ODE) is introduced for each resulting optimization problem. The convergence of each ODE solution is proved for any starting point. The limit of each ODE solution for any starting point is fully studied. Both the extreme and the interior eigenvalues and their corresponding eigenvectors can be easily obtained under a very mild condition. Promising numerical results are also presented.     

On convergence of the inexact Rayleigh quotient iteration with MINRES

For the Hermitian inexact Rayleigh quotient iteration (RQI), we present a new general theory, independent of iterative solvers for shifted inner linear systems. The theory shows that the method converges at least quadratically under a new condition, called the uniform positiveness condition, that may allow the residual norm _ξk≥1${\xi }_k\ge 1$ of the inner linear system at outer iteration k+1$k+1$ and can be considerably weaker than the condition _ξk≤ξ<1${\xi }_k\le \xi <1$ with ξ$\xi$ a constant not near one commonly used in the literature. We consider the convergence of the inexact RQI with the unpreconditioned and tuned preconditioned MINRES methods for the linear systems. Some attractive properties are derived for the residuals obtained by MINRES. Based on them and the new general theory, we make a refined analysis and establish a number of new convergence results. Let ‖_rk‖$\Vert r_k\Vert$ be the residual norm of approximating eigenpair at outer iteration k$k$. Then all the available cubic and quadratic convergence results require _ξk=O(‖_rk‖)${\xi }_k=O\left(\Vert r_k\Vert \right)$ and _ξk≤ξ${\xi }_k\le \xi$ with a fixed ξ$\xi$ not near one, respectively. Fundamentally different from these, we prove that the inexact RQI with MINRES generally converges cubically, quadratically and linearly provided that _ξk≤ξ${\xi }_k\le \xi$ with a constant ξ<1$\xi <1$ not near one, _ξk=1−O(‖_rk‖)${\xi }_k=1-O\left(\Vert r_k\Vert \right)$ and _ξk=1−O(‖_rk‖²)${\xi }_k=1-O\left({\Vert r_k\Vert }^2\right)$, respectively. The new convergence conditions are much more relaxed than ever before. The theory can be used to design practical stopping criteria to implement the method more effectively. Numerical experiments confirm our results.     

Isospectral flow method for nonnegative inverse eigenvalue problem with prescribed structure

The nonnegative inverse eigenvalue problem is that given a family of complex numbers λ={λ₁,…,λ_n}, find a nonnegative matrix of order n with spectrum λ. This problem is difficult and remains unsolved partially. In this paper, we focus on its generalization that the reconstructed nonnegative matrices should have some prescribed entries. It is easy to see that this new problem will come back to the common nonnegative inverse eigenvalue problem if there is no constraint of the locations of entries. A numerical isospectral flow method which is developed by hybridizing the optimization theory and steepest descent method is used to study the reconstruction. Moreover, an error estimate of the numerical iteration for ordinary differential equations on the matrix manifold is presented. After that, a numerical method for the nonnegative symmetric inverse eigenvalue problem with prescribed entries and its error estimate are considered. Finally, the approaches are verified by the numerical test results.     

A modified harmonic block Arnoldi algorithm with adaptive shifts for large interior eigenproblems

The harmonic block Arnoldi method can be used to find interior eigenpairs of large matrices. Given a target point or shift τ$\tau$ to which the needed interior eigenvalues are close, the desired interior eigenpairs are the eigenvalues nearest τ$\tau$ and the associated eigenvectors. However, it has been shown that the harmonic Ritz vectors may converge erratically and even may fail to do so. To do a better job, a modified harmonic block Arnoldi method is coined that replaces the harmonic Ritz vectors by some modified harmonic Ritz vectors. The relationships between the modified harmonic block Arnoldi method and the original one are analyzed. Moreover, how to adaptively adjust shifts during iterations so as to improve convergence is also discussed. Numerical results on the efficiency of the new algorithm are reported.     

Block-Arnoldi and Davidson methods for unsymmetric large eigenvalue problems

Summary We present two methods for computing the leading eigenpairs of large sparse unsymmetric matrices. Namely the block-Arnoldi method and an adaptation of the Davidson method to unsymmetric matrices. We give some theoretical results concerning the convergence and discuss implementation aspects of the two methods. Finally some results of numerical tests on a variety of matrices, in which we compare these two methods are reported.     

A numerical method for minimum distance estimation problems

This paper introduces a general method for the numerical derivation of a minimum distance (MD) estimator for the parameters of an unknown distribution. The approach is based on an active sampling of the space in which the random sample takes values and on the optimization of the parameters of a suitable approximating model. This allows us to derive the MD estimator function for any given distribution, by which we can immediately obtain the MD estimate of the unknown parameters in correspondence to any observed random sample. Convergence of the method is proved when mild conditions on the sampling process and on the involved functions are satisfied, and it is shown that favorable rates can be obtained when suitable deterministic sequences are employed. Finally, simulation results are provided to show the effectiveness of the proposed algorithm on two case studies.     

A Wilkinson-like multishift QR algorithm for symmetric eigenvalue problems and its global convergence

In 1989, Bai and Demmel proposed the multishift QR algorithm for eigenvalue problems. Although the global convergence property of the algorithm (i.e., the convergence from any initial matrix) still remains an open question for general nonsymmetric matrices, in 1992 Jiang focused on symmetric tridiagonal case and gave a global convergence proof for the generalized Rayleigh quotient shifts. In this paper, we propose Wilkinson-like shifts, which reduce to the standard Wilkinson shift in the single shift case, and show a global convergence theorem.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

A proximal point algorithm for minimax problems

This paper presents a proximal point algorithm for solving discretel _∞ approximation problems of the form minimize ∥Ax−b∥_∞. Let ε_∞ be a preassigned positive constant and let ε _l ,l = 0,1,2,... be a sequence of positive real numbers such that 0 < ε _l < ε_∞. Then, starting from an arbitrary pointz ₀, the proposed method generates a sequence of points z _l ,l= 0,1,2,..., via the rule . One feature that characterizes this algorithm is its finite termination property. That is, a solution is reached within a finite number of iterations. The smaller are the numbers ε _l the smaller is the number of iterations. In fact, if ε ₀ is sufficiently small then z₁ solves the original minimax problem. The practical value of the proposed iteration depends on the availability of an efficient code for solving a regularized minimax problem of the form minimize where ∈ is a given positive constant. It is shown that the dual of this problem has the form maximize , and ify solves the dual thenx=A ^T y solves the primal. The simple structure of the dual enables us to apply a wide range of methods. In this paper we design and analyze a row relaxation method which is suitable for solving large sparse problems. Numerical experiments illustrate the feasibility of our ideas.     

A spatial domain decomposition method for parabolic optimal control problems

We present a non-overlapping spatial domain decomposition method for the solution of linear–quadratic parabolic optimal control problems. The spatial domain is decomposed into non-overlapping subdomains. The original parabolic optimal control problem is decomposed into smaller problems posed on space–time cylinder subdomains with auxiliary state and adjoint variables imposed as Dirichlet boundary conditions on the space–time interface boundary. The subdomain problems are coupled through Robin transmission conditions. This leads to a Schur complement equation in which the unknowns are the auxiliary state adjoint variables on the space-time interface boundary. The Schur complement operator is the sum of space–time subdomain Schur complement operators. The application of these subdomain Schur complement operators is equivalent to the solution of an subdomain parabolic optimal control problem. The subdomain Schur complement operators are shown to be invertible and the application of their inverses is equivalent to the solution of a related subdomain parabolic optimal control problem. We introduce a new family of Neumann–Neumann type preconditioners for the Schur complement system including several different coarse grid corrections. We compare the numerical performance of our preconditioners with an alternative approach recently introduced by Benamou.     

Deflated block Krylov subspace methods for large scale eigenvalue problems

We discuss a class of deflated block Krylov subspace methods for solving large scale matrix eigenvalue problems. The efficiency of an Arnoldi-type method is examined in computing partial or closely clustered eigenvalues of large matrices. As an improvement, we also propose a refined variant of the Arnoldi-type method. Comparisons show that the refined variant can further improve the Arnoldi-type method and both methods exhibit very regular convergence behavior.     

Newton's method for a class of nonsmooth functions

This paper presents and justifies a Newton iterative process for finding zeros of functions admitting a certain type of approximation. This class includes smooth functions as well as nonsmooth reformulations of variational inequalities. We prove for this method an analogue of the fundamental local convergence theorem of Kantorovich including optimal error bounds.The research reported here was sponsored by the National Science Foundation under Grants CCR-8801489 and CCR-9109345, by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and F49620-93-1-0068, by the U. S. Army Research Office under Grant No. DAAL03-92-G-0408, and by the U. S. Army Space and Strategic Defense Command under Contract No. DASG60-91-C-0144. The U. S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

A practical termination criterion for the conjugate gradient method

The conjugate gradient method for the iterative solution of a set of linear equationsAx=b is essentially equivalent to the Lanczos method, which implies that approximations to certain eigen-values ofA can be obtained at low cost. In this paper it is shown how the smallest active eigenvalue ofA can be cheaply approximated, and the usefulness of this approximation for a practical termination criterion for the conjugate gradient method is studied. It is proved that this termination criterion is reliable in many relevant situations.     

Discretization of multiparameter eigenvalue problems

Summary Although multiparameter eigenvalue problems, as for example Mathieu's differential equation, have been known for a long time, so far no work has been done on the numerical treatment of these problems. So in this paper we extend the spectral theory for one parameter (cf. [7, II, VII]) to multiparameter eigenvalue problmes, formulate in the framework of discrete approximation a convergent numerical treatment, establish algebraic bifurcation equations for the intersection points of the eigenvalue curves and illustrate this with some numerical examples.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

BTTB preconditioners for BTTB least squares problems

In this paper, we consider solving the least squares problem min_x‖b-Tx‖₂ by using preconditioned conjugate gradient (PCG) methods, where T is a large rectangular matrix which consists of several square block-Toeplitz-Toeplitz-block (BTTB) matrices and b is a column vector. We propose a BTTB preconditioner to speed up the PCG method and prove that the BTTB preconditioner is a good preconditioner. We then discuss the construction of the BTTB preconditioner. Numerical examples, including image restoration problems, are given to illustrate the efficiency of our BTTB preconditioner. Numerical results show that our BTTB preconditioner is more efficient than the well-known Level-1 and Level-2 circulant preconditioners.     

On computingINV block preconditionings for the conjugate gradient method

The INV(k) and MINV(k) block preconditionings for the conjugate gradient method require generation of selected elements of the inverses of symmetric matrices of bandwidth 2k+1. Generalizing the previously describedk=1 (tridiagonal) case tok=2, explicit expressions for the inverse elements of a symmetric pentadiagonal matrix in terms of Green's matrix of rank two are given. These expressions are found to be seriously ill-conditioned; hence alternative computational algorithms for the inverse elements must be used. Behavior of thek=1 andk=2 preconditionings are compared for some discretized elliptic partial differential equation test problems in two dimensions.Presented by the first author at the Joint U.S.-Scandinavian Symposium on Scientific Computing and Mathematical Modeling, January 1985, in honor of Germund Dahlquist on the occasion of his 60th birthday. This work was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE AC03-76SF00098.     

A Levenberg–Marquardt method for estimating polygonal regions

The problem is considered of the estimation of a polygonal region in two dimensions from data approximately marking the outline of the region. A solution is sought by formulating and solving a nonlinear least squares problem. A Levenberg–Marquardt method is developed for this problem, with an implementation which exploits the special structure so that the Levenberg–Marquardt step can be computed efficiently.     

A generalized successive overrelaxation method for least squares problems

In this paper a new iterative method is given for solving large sparse least squares problems and computing the minimum norm solution to underdetermined consistent linear systems. The new scheme is called the generalized successive overrelaxation (GSOR) method and is shown to be convergent ifA is full column rank. The GSOR method involves a parameter ρ and an auxiliary matrixP. One can choose matrix P so that the GSOR method only involves matrix and vector operations; therefore the GSOR method is suitable for parallel computations. Besides, the GSOR method can be combined with preconditioning techniques, and therefore can be expected to be more effective. This author's work was supported by Natural Science Foundation of Liaoning Province, China.