Square-root Householder subspace tracking

A class of singular value decomposition (SVD)-type subspace trackers based on the overdetermined row-Householder principle is introduced. These algorithms are maximally fast with a dominant operations count of 3Nr multiplications per time update. They can be regarded as square-root forms of previously introduced conventional fast subspace trackers and offer interesting features such as perfectly orthonormal basis estimates, lowest dynamic range requirements, and highest numerical robustness and stability. Several variants of the method are proposed and studied experimentally.     

Augmented Block Householder Arnoldi Method

Computing the eigenvalues and eigenvectors of a large sparse nonsymmetric matrix arises in many applications and can be a very computationally challenging problem. In this paper we propose the Augmented Block Householder Arnoldi (ABHA) method that combines the advantages of a block routine with an augmented Krylov routine. A public domain MATLAB code ahbeigs has been developed and numerical experiments indicate that the code is competitive with other publicly available codes.     

关于镜面反射矩阵的注记

涉及到矩阵分解时,镜面反射矩阵起着非常重要的作用.讨论镜面反射矩阵的若干性质,给出了镜面反射矩阵一个重要性质的逆命题.即当n阶Hermite矩阵的特征值与镜面反射矩阵的特征值相同时,该Hermite矩阵恰好是一个镜面反射矩阵.     

Householder矩阵的又一特性

给出了Householder矩阵的其它若干性质,利用本文中得到的正交向量组所对应的Householder矩阵的重要性质,解决了形如A=k1H1 k2H2 … knHn(ki∈R,Hi为n阶Householder矩阵,i=1,2,…n)的实对称阵的特性值与特征向量的问题,且任一实对称矩阵A均可表示为上述形式.     

Modified Householder iterative method for nonlinear equations

In this paper, we suggest and analyze a new two-step predictor–corrector type iterative method for solving nonlinear equations of the type f(x)=0. This new method includes the two-step Newton method as a special case. We show that this new two-step method is a sixth-order convergent method. Several examples are given to illustrate the efficiency of this new method and its comparison with other sixth-order methods. This method can be considered as a significant improvement of the Newton method and its variant forms.     

On updating triangular products of Householder reflections

Summary In this paper it is shown how a triangular product of Householder reflections can be updated with an arbitrary elementary orthogonal transformation. The amount of work required is 5/2n ² multiplications for absorbing an arbitrary reflection and 3n ² multiplications for absorbing a plane rotation on subsequent indices.     

Real matrix homotopies based on Householder reflections

Anexplicithomotopyisconstructedbetweentheidentitymatrixandanarbitraryrealmatrixwithpositivedeterminant.Theconstructionrequiresnoeigenvalueinformationandyieldsasmoothparameterizationforwhichthematrixdeterminantremainspositiveandvariesas a monotonic or unimodal function of the parameter. The key idea of the construction is that a simple formula smoothly transforms any product of two Householder reflections to the identity.     

Generation of finite tight frames by Householder transformations

Finite tight frames are widely used for many applications. An important problem is to construct finite frames with prescribed norm for each vector in the tight frame. In this paper we provide a fast and simple algorithm for such a purpose. Our algorithm employs the Householder transformations. For a finite tight frame consisting of m vectors in ?ⁿ or ?ⁿ only O(nm) operations are needed. In addition, we also study the following question: Given a set of vectors in ?ⁿ or ?ⁿ, how many additional vectors, possibly with constraints, does one need to add in order to obtain a tight frame?     

Solving inverse eigenvalue problems via Householder and rank-one matrices

A brief and practical algorithm is introduced to solve symmetric inverse eigenvalue problems, which we call HROU algorithm. The algorithm is based on Householder transformations and rank one updating. We give some basic properties and the computational amount and develop sensitivity analysis of HROU algorithm. Furthermore, we develop HROU algorithm into a multi-level and adaptive one, named MLAHROU, to solve symmetric nonnegative inverse eigenvalue problems. New sufficient conditions to ensure symmetric nonnegative matrices and symmetric M-matrices are given. Many numerical examples are given to verify our theory, compare with existing results and show the efficiency of our algorithms.     

Convergence Analysis of the Block Householder Block Diagonalization Algorithm

This paper develops algebraic and convergence properties of the left and right block reflectors used in the block diagonalization algorithm. Several numerical illustrations are reported.AMS subject classification (2000) 65F20, 15A23.Submitted December 2002. Accepted October 2003. Communicated by Per Christian Hansen.     

Equivalence between modified symplectic Gram-Schmidt and Householder SR algorithms

The SR factorization for a given matrix A is a QR-like factorization A=SR, where the matrix S is symplectic and R is J-upper triangular. This factorization is fundamental for some important structure-preserving methods in linear algebra and is usually implemented via the symplectic Gram-Schmidt algorithm (SGS). There exist two versions of SGS, the classical (CSGS) and the modified (MSGS). Both are equivalent in exact arithmetic, but have very different numerical behaviors. The MSGS is more stable. Recently, the symplectic Householder SR algorithm has been introduced, for computing efficiently the SR factorization. In this paper, we show two new and important results. The first is that the SR factorization of a matrix A via the MSGS is mathematically equivalent to the SR factorization via Householder SR algorithm of an embedded matrix. The later is obtained from A by adding two blocks of zeros in the top of the first half and in the top of the second half of the matrix A. The second result is that MSGS is also numerically equivalent to Householder SR algorithm applied to the mentioned embedded matrix.