A blocked QR-decomposition for the parallel symmetric eigenvalue problem

In this paper we present a new stable algorithm for the parallel QR-decomposition of “tall and skinny” matrices. The algorithm has been developed for the dense symmetric eigensolver ELPA, where the QR-decomposition of tall and skinny matrices represents an important substep. Our new approach is based on the fast but unstable CholeskyQR algorithm (Stathopoulos and Wu, 2002) [1]. We show the stability of our new algorithm and provide promising results of our MPI-based implementation on a BlueGene/P and a Power6 system.     

A parallel Lanczos method for symmetric generalized eigenvalue problems

The Lanczos algorithm is a very effective method for finding extreme eigenvalues of symmetric matrices. In this paper, we present our parallel version of the Lanczos method for symmetric generalized eigenvalue problem, PLANSO. PLANSO is based on a sequential package called LANSO which implements the Lanczos algorithm with partial reorthogonalization. It is portable to all parallel machines that support MPI and it is easy to interface with most parallel computing packages. Through numerical experiments, we demonstrate that it achieves similar parallel efficiency as PARPACK, but uses considerably less time. Received: 21 January 1998 / Accepted: 10 June 1999     

A parallel method for computing the generalized singular value decomposition

We describe a new parallel algorithm for computing the generalized singular value decomposition of two n × n matrices, one of which is nonsingular. Our procedure requires O(n) time and one triangular array of O(n²) processors.     

The projective power method for the algebraic eigenvalue problem

A new method for computing several largest eigenvalues of a matrix has some common features with the power method but uses orthogonal projections instead of the customary ways of deflation. The rate of convergence is basically the same as for the power method but the fast refinement of the approximations to eigenvalues and eigenvectors in the cases of real symmetric and Hermitian matrices can be done even without the inverse iterations.     

On the scaled newton method for the symmetric eigenvalue problem

For solving symmetric eigenvalue problems the scaled Newton method is proposed. The new algorithm is equivalent to the Rayleigh quotient iteration and its rate of convergence is cubic. Numerical experiments indicate that the scaled Newton method is very competitive with the projected Newton method, and produces, in the main, insignificantly smaller residua than the Rayleigh quotient iteration.     

A parallel method for large sparse generalized eigenvalue problems using a GridRPC system

In this paper we present a master–worker type parallel method for finding several eigenvalues and eigenvectors of a generalized eigenvalue problem , where A and B are large sparse matrices. A moment-based method that finds all of the eigenvalues that lie inside a given domain is used. In this method, a small matrix pencil that has only the desired eigenvalues is derived by solving large sparse systems of linear equations constructed from A and B. Since these equations can be solved independently, we solve them on remote servers in parallel. This approach is suitable for master–worker programming models. We have implemented and tested the proposed method in a grid environment using a grid RPC (remote procedure call) system called OmniRPC. The performance of the method on PC clusters that were used over a wide-area network was evaluated.     

Two-level quadratic equal-order stabilized method for the Stokes eigenvalue problem

In this article, the P₂?P₂-stabilized finite element method based on two local Gaussian quadratures is applied to discretize the Stokes eigenvalue problem, and the corresponding convergence analysis is given. Furthermore, a two-level scheme, which solves the Stokes eigenvalue problem on a coarser grid and a Stokes problem on the fine grid, is employed to reduce the computational cost. Numerical examples are given to confirm the theoretical results.     

A uniformly accurate spline collocation method for a singular perturbation problem

We present a spline difference scheme derived from a «comparison problem» which uses piecewise-constant and piecewise-cubic interpolatory polynomials as an approximation to the driving terms in the self-adjoint perturbation problem. Numerical evidence is included.     

Convergence of a lowest-order finite element method for the transmission eigenvalue problem

The transmission eigenvalue problem arises in scattering theory. The main difficulty in its analysis is the fact that, depending on the chosen formulation, it leads either to a quadratic eigenvalue problem or to a non-classical mixed problem. In this paper we prove the convergence of a mixed finite element approximation. This approach, which is close to the Ciarlet–Raviart discretization of biharmonic problems, is based on Lagrange finite elements and is one of the less expensive methods in terms of the amount of degrees of freedom. The convergence analysis is based on classical abstract spectral approximation result and the theory of mixed finite element methods for solving the stream function–vorticity formulation of the Stokes problem. Numerical experiments are reported in order to assess the efficiency of the method.     

A vector-multiplication dominated parallel algorithm for the computation of real eigenvalue spectra

In order to exploit effectively the power of array and vector processors for the numerical solution of linear algebraic problems it is desirable to express algorithms principally in terms of vector and matrix operations. Algorithms which manipulate vectors and matrices at component level are best suited for execution on single processor hardware. Often, however, it is difficult, if not impossible, to construct efficient versions of such algorithms which are suitable foe execution on parallwl hardware. A method for computing the eigenvalues of real unsymmetric matrices with real eigenvalue spectra is presented. The method is an extension of the one described in ref. [1]. The algorithm makes heavy use of vector inner product evaluations. The manipulation of individual components of vectors and matrices is kept to a minimum. Essentially, the method involves the construction of a sequence of biorthogonal transformation matrices the combined effect of which is to diagonalise the matrix. The eigenvalues of the matrix are diagonal elements of the final diagonalised form. If the eigenvectors of the matrix are also required the algorithm may be extended in a straightforward way. The effectiveness of the algorithm is demonstrated by an application of sequential version to several small matrices and some comments are made about the time complexity of the parallel version.     

A parallel approach to the modified Numerov-like eigenvalue determination for sturm-Liouville problems

A modified Numerov-like eigenvalue algorithm, previously introduced, is parallelized. An inplementation of this algorithm on a Helios based parallel processing transputer system is discussed. Time savings with respect to a sequential approach are commented.     

The group-coordinate relaxation method for solving the generalized eigenvalue problem for large real-symmetric matrices

A method is described for solving the generalized eigenvalue problem for very large matrices which are not sparse and in which the off-diagonal elements are not small compared with the diagonal ones. This method has been found to succeed where others have failed.     

A numerical solution of the membrane eigenvalue problem

A conformal transformation method is used for the numerical solution of the membrane eigenvalue problem. The method overcomes, in many cases, the difficulties associated with the computation of the eigenvalues of problems involving curved boundaries and/or boundary singularities and produces accurate numerical approximations. This is achieved by transforming the original problem into another computationally simpler one.     

A parallel algorithm for the integer knapsack problem

A sequential algorithm with complexity O(M²+n) for the integer knapsack problem is presented. M is the capacity of the knapsack, and n the number of objects. The algorithm admits an efficient parallelization on a p-processor ring machine. The corresponding parallel algorithm is O(M²/p+n). The parallel algorithm is compared with a version of the well-known Lee algorithm adapted to the integer knapsack problem. Computational results on both a local area network and a transputer are reported.     

A parallel two-list algorithm for the knapsack problem

An n-element knapsack problem has 2ⁿ possible solutions to search over, so a task which can be accomplished in 2″ trials if an exhaustive search is used. Due to the exponential time in solving the knapsack problem, the problem is considered to be very hard. In the past decade, much effort has been done in order to find techniques which could lead to practical algorithms with reasonable running time. In 1994, Chang et al. proposed a brilliant parallel algorithm, which needs O(2^n/8) processors to solve the knapsack problem in O(2^n/2) time; that is, the cost of Chang et al.'s parallel algorithm is O(2^5n/8). In this paper, we propose a parallel algorithm to improve Chang et al.'s parallel algorithm by reducing the time complexity to be O(2^3n/8) under the same O(2^n/8) processors available. Thus, the proposed parallel algorithm has a cost of O(2^n/2). It is an improvement over previous literature. We believe that the proposed parallel algorithm is pragmatically feasible at the moment when multiprocessor systems become more and more popular.     

An efficient implementation of parallel eigenvalue computation for massively parallel processing

This paper describes an efficient implementation and evaluation of a parallel eigensolver for computing all eigenvalues of dense symmetric matrices. Our eigensolver uses a Householder tridiagonalization method, which has higher parallelism and performance than conventional methods when problem size is relatively small, e.g., the order of 10,000. This is very important for relevant practical applications, where many diagonalizations for such matrices are required so often. The routine was evaluated on the 1024 processors HITACHI SR2201, and giving speedup ratios of about 2–5 times as compared to the ScaLAPACK library on 1024 processors of the HITACHI SR2201.     

The eigenvalue problem for banded matrices

The generalized Lanczos method is used for the purpose of calculating frequencies and mode shapes for linearly elastic discretized structures where the energy-consistent stiffness and mass matrices are equally banded. This approach involves reduction of the problem to standard tridiagonal form without expanding the band width of either of the original arrays. Applications of the method to both vibrational and buckling analyses indicate its potential for conserving core storage when solving the eigenvalue problem on a digital computer.     

A quadratic eigenvalue problem involving Stokes equations

An existence theorem for the eigenvalues of a spectral problem is studied in this paper. The physical situation behind this mathematical problem is the determination of the eigenfrequencies and eigenmotions of a fluid-solid structure. The liquid part in this structure is represented by a viscous incompressible fluid, while the solid part is a set of parallel rigid tubes. The spectral problem governing this system is a quadratic eigenvalue problem which involves Stokes equations with a non-local boundary condition. The strategy for tackling the question of existence of eigenvalues consists of proving that the original problem is equivalent to that of determining the characteristic values of a linear (non-selfadjoint) compact operator. Sharp estimates for the eigenvalues give precise information about the region of ω where the eigenvalues are located. In particular, we prove that this problem admits a countable set of eigenvalues in which only a finite number of them have a non-zero imaginary part.