GIVENS正交三角化的列超前并行消去算法

在分析已有的Ｇｉｖｅｎｓ正交三角化并行算法的基础上，进一步分析了在ＭＩＭＤ并行系统上行反射交替存储的逐次Ｇｉｖｅｎｓ正交三角化并行过程，提出了列超前并行消去算法，还介绍了这个算法在ＭＩＭＤ并行系统上实现的主要技巧，证明了列超前并行消去算法的并行加速倍数Ｓｐ与处理机台数Ｐ十分接近．     

求解场问题的一种新算法

基于文（１）（２），本文给出了一种计算场问题的新算法－拓扑有限元Ｇｉｖｅｎｓ算法，该方法利用了拓扑有限元的特性及快速Ｇｉｖｅｎｓ变换。算例结果与实验吻合很好。     

A Class of Incomplete Orthogonal Factorization Methods. II: Implementation and Results

We present, implement and test several incomplete QR factorization methods based on Givens rotations for sparse square and rectangular matrices. For square systems, the approximate QR factors are used as right-preconditioners for GMRES, and their performance is compared to standard ILU techniques. For rectangular matrices corresponding to linear least-squares problems, the approximate R factor is used as a right-preconditioner for CGLS. A comprehensive discussion is given about the uses, advantages and shortcomings of the preconditioners. AMS subject classification (2000) 65F10, 65F25, 65F50.Received May 2002. Revised October 2004. Communicated by Åke Björck.     

A note on hyperbolic transformations

We shall discuss the so‐called hyperbolic Householder and Givens transformations applied to complex matrices, including the case of zero hyperbolic energy of a transformed vector. For each case a numerically stable algorithm is available. Copyright © 2001 John Wiley & Sons, Ltd.     

A note on the recursive calculation of dominant singular subspaces

A recursive procedure for computing an approximation of the left and right dominant singular subspaces of a given matrix is proposed in [1]. The method is particularly suited for matrices with many more rows than columns. The procedure consists of a few steps. In one of these steps a Householder transformation is multiplied to an upper triangular matrix. The following step consists in recomputing an upper triangular matrix from the latter product. In [1] it is said that the latter step is accomplished in O(k³) operations, where k is the order of the triangular matrix. In this short note we show that this step can be accomplished in O(k²) operations. This research was partially supported by MIUR, grant number 2002014121 (first author) and by the Research Council K.U.Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann–Hilbert problems, random matrices and Padé–Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Ministers Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling) (second and third author). The scientific responsibility rests with the authors.AMS subject classification 15A15, 15A09, 15A23     

Preconditioned GMRES methods with incomplete Givens orthogonalization method for large sparse least-squares problems

We propose to precondition the GMRES method by using the incomplete Givens orthogonalization (IGO) method for the solution of large sparse linear least-squares problems. Theoretical analysis shows that the preconditioner satisfies the sufficient condition that can guarantee that the preconditioned GMRES method will never break down and always give the least-squares solution of the original problem. Numerical experiments further confirm that the new preconditioner is efficient. We also find that the IGO preconditioned BA-GMRES method is superior to the corresponding CGLS method for ill-conditioned and singular least-squares problems.     

A new Jacobi-like method for joint diagonalization of arbitrary non-defective matrices

This paper addresses the problem of joint diagonalization of a set of matrices. A new Jacobi-Like method that has the advantages of computational efficiency and of generality is presented. The proposed algorithm brings the general matrices into normal ones and performs a joint diagonalization by a combination of unitary and shears (non-unitary) transformations. It is based on the iterative minimization of an appropriate cost function using generalized Jacobi rotation matrices.     

Extracting more than a few eigenvectors from a dense real symmetric matrix: Optimal algorithms versus the architectural constraints of the FPS-X64

Ten widely available sets of routines, including HQRII, QCPE GIVENS and EISPACK 3, were evaluated for reliability, robustness, accuracy, speed, compactness, portability and simplicity. All were found lacking in one or more areas. Modified versions of the EISPACK routines TRED3, TQLRAT, TINVIT and TRBAK3 performed somewhat better. Changes to TINVIT were especially important for improved speed, accuracy and reliability. To achieve the maximum capabilities of the FPS-X64 series of computers access to table memory is required, but since the FORTRAN compiler does not allow this and there is no library support for the required operations, it was necessary to write three routines in APAL. The standard algorithm needs to be modified before full efficiency can be achieved for the back transformation.Operated for the US Department of Energy by Iowa State University under contract no. W-74-05-ENG-82. This work was supported by the Office of Basic Energy Sciences     

Orthogonal Laurent polynomials on the unit circle and snake-shaped matrix factorizations

Let there be given a probability measure μ on the unit circle of the complex plane and consider the inner product induced by μ. In this paper we consider the problem of orthogonalizing a sequence of monomials {z^r_k}_k, for a certain order of the , by means of the Gram–Schmidt orthogonalization process. This leads to a sequence of orthonormal Laurent polynomials {ψ_k}_k. We show that the matrix representation with respect to {ψ_k}_k of the operator of multiplication by z is an infinite unitary or isometric matrix allowing a ‘snake-shaped’ matrix factorization. Here the ‘snake shape’ of the factorization is to be understood in terms of its graphical representation via sequences of little line segments, following an earlier work of S. Delvaux and M. Van Barel. We show that the shape of the snake is determined by the order in which the monomials {z^r_k}_k are orthogonalized, while the ‘segments’ of the snake are canonically determined in terms of the Schur parameters for μ. Isometric Hessenberg matrices and unitary five-diagonal matrices (CMV matrices) follow as a special case of the presented formalism.     

GIVENS正交三角化列超前并行消去法的实现

介绍了Ｇｉｖｅｎｓ正交三角化列超前并行消去算法（ＣＥＡＰ算法）的实现方法和计算过程，包括确定主台台号，在主台形成控制向量，通过控制向量控制列超前并行消去等．