Perturbation analysis for the symplectic QR factorization

In this paper, the perturbation analysis for the symplectic QR factorization is considered. Some first-order and rigorous normwise perturbation bounds with normwise or componentwise perturbations in the given matrix are presented.     

New perturbation bounds and condition numbers for the hyperbolic QR factorization

Using the modified matrix-vector equation approach, the technique of Lyapunov majorant function and the Banach fixed point theorem, we obtain some new rigorous perturbation bounds for R factor of the hyperbolic QR factorization under normwise perturbation. These bounds are always tighter than the one given in the literature. Moreover, the optimal first-order perturbation bounds and the normwise condition numbers for the hyperbolic QR factorization are also presented.     

A Lanczos‐type algorithm for the QR factorization of regular Cauchy matrices

We present a fast algorithm for computing the QR factorization of Cauchy matrices with real nodes. The algorithm works for almost any input matrix, does not require squaring the matrix, and fully exploits the displacement structure of Cauchy matrices. We prove that, if the determinant of a certain semiseparable matrix is non‐zero, a three term recurrence relation among the rows or columns of the factors exists. Copyright © 2002 John Wiley & Sons, Ltd.     

A block Cholesky-LU-based QR factorization for rectangular matrices

The Householder method provides a stable algorithm to compute the full QR factorization of a general matrix. The standard version of the algorithm uses a sequence of orthogonal reflections to transform the matrix into upper triangular form column by column. In order to exploit (level 3 BLAS or structured matrix) computational advantages for block-partitioned algorithms, we develop a block algorithm for the QR factorization. It is based on a well-known block version of the Householder method which recursively divides a matrix columnwise into two smaller matrices. However, instead of continuing the recursion down to single matrix columns, we introduce a novel way to compute the QR factors in implicit Householder representation for a larger block of several matrix columns, that is, we start the recursion at a block level instead of a single column. Numerical experiments illustrate to what extent the novel approach trades some of the stability of Householder's method for the computational efficiency of block methods.     

QR factorization for row or column symmetric matrix

The problem of fast computing the QR factorization of row or column symmetric matrix is considered. We address two new algorithms based on a correspondence of Q and R matrices between the row or column symmetric matrix and its mother matrix. Theoretical analysis and numerical evidence show that, for a class of row or column symmetric matrices, the QR factorization using the mother matrix rather than the row or column symmetric matrix per se can save dramatically the CPU time and memory without loss of any numerical precision.     

Asymptotic properties of the QR factorization of banded Hessenberg–Toeplitz matrices

We consider Givens QR factorization of banded Hessenberg–Toeplitz matrices of large order and relatively small bandwidth. We investigate the asymptotic behaviour of the R factor and Givens rotation when the order of the matrix goes to infinity, and present some interesting convergence properties. These properties can lead to savings in the computation of the exact QR factorization and give insight into the approximate QR factorizations of interest in preconditioning. The properties also reveal the relation between the limit of the main diagonal elements of R and the largest absolute root of a polynomial. Copyright © 2005 John Wiley & Sons, Ltd.     

Componentwise perturbation analyses for the QR factorization

Summary. This paper gives componentwise perturbation analyses for Q and R in the QR factorization A=QR, , R upper triangular, for a given real $m\times n$ matrix A of rank n. Such specific analyses are important for example when the columns of A are badly scaled. First order perturbation bounds are given for both Q and R. The analyses more accurately reflect the sensitivity of the problem than previous such results. The condition number for R is bounded for a fixed n when the standard column pivoting strategy is used. This strategy also tends to improve the condition of Q, so usually the computed Q and R will both have higher accuracy when we use the standard column pivoting strategy. Practical condition estimators are derived. The assumptions on the form of the perturbation are explained and extended. Weaker rigorous bounds are also given. Received April 11, 1999 / Published online October 16, 2000     

Multifrontal QR Factorization in a Multiprocessor Environment

We describe the design and implementation of a parallel QR decomposition algorithm for a large sparse matrix A . The algorithm is based on the multifrontal approach and makes use of Householder transformations. The tasks are distributed among processors according to an assembly tree which is built from the symbolic factorization of the matrix A ^T A . We first address uniprocessor issues and then discuss the multiprocessor implementation of the method. We consider the parallelization of both the factorization phase and the solve phase. We use relaxation of the sparsity structure of both the original matrix and the frontal matrices to improve the performance. We show that, in this case, the use of Level 3 BLAS can lead to very significant gains in performance. We use the eight processor Alliant˜FX/80 at CERFACS to illustrate our discussion.     

Regularization Using QR Factorization and the Estimation of the Optimal Parameter

In this paper we propose a direct regularization method using QR factorization for solving linear discrete ill-posed problems. The decomposition of the coefficient matrix requires less computational cost than the singular value decomposition which is usually used for Tikhonov regularization. This method requires a parameter which is similar to the regularization parameter of Tikhonov's method. In order to estimate the optimal parameter, we apply three well-known parameter choice methods for Tikhonov regularization.This revised version was published online in October 2005 with corrections to the Cover Date.     

Indefinite QR Factorization

Let A be a Hermitian positive definite matrix given by its rectangular factor G such that A=G^*G. It is well known that the Cholesky factorization of A is equivalent to the QR factorization of G. In this paper, an analogue of the QR factorization for Hermitian indefinite matrices is constructed. This problem has been considered by many authors, but the problem of zero diagonal elements has not been solved so far. Here we show how to overcome this difficulty. AMS subject classification (2000) 65F25, 46C20, 65F15     

Low-rank revealing QR factorizations

Rank revealing factorizations are used extensively in signal processing in connection with, for example, linear prediction and signal subspace algorithms. We present an algorithm for computing rank revealing QR factorizations of low-rank matrices. The algorithm produces tight upper and lower bounds for all the largest singular values, thus making it particularly useful for treating rank deficient problems by means of subset selection, truncated QR, etc. The algorithm is similar in spirit to an algorithm suggested earlier by Chan for matrices with a small nullity, and it can also be considered as an extension of ordinary column pivoting.     

双曲矩阵分解修正问题的一些结果

This paper considers the updating problem of the hyperbolic matrix factorizations. The sufficient conditions for the existence of the updated hyperbolic matrix factorizations are first provided. Then, some differential inequalities and first order perturbation expansions for the updated hyperbolic factors are derived. These results generalize the corresponding ones for the updating problem of the classical QR factorization obtained by Jiguang SUN.     

Bounds on Singular Values Revealed by QR Factorizations

We introduce a pair of dual concepts: pivoted blocks and reverse pivoted blocks. These blocks are the outcome of a special column pivoting strategy in QR factorization. Our main result is that under such a column pivoting strategy, the QR factorization of a given matrix can give tight estimates of any two a priori-chosen consecutive singular values of that matrix. In particular, a rank-revealing QR factorization is guaranteed when the two chosen consecutive singular values straddle a gap in the singular value spectrum that gives rise to the rank degeneracy of the given matrix. The pivoting strategy, called cyclic pivoting, can be viewed as a generalization of Golub's column pivoting and Stewart's reverse column pivoting. Numerical experiments confirm the tight estimates that our theory asserts.     

Stochastic perturbation approach to the wavelet‐based analysis

The wavelet‐based decomposition of random variables and fields is proposed here in the context of application of the stochastic second order perturbation technique. A general methodology is employed for the first two probabilistic moments of a linear algebraic equations system solution, which are obtained instead of a single solution projection in the deterministic case. The perturbation approach application allows determination of the closed formulas for a wavelet decomposition of random fields. Next, these formulas are tested by symbolic projection of some elementary random field. Copyright © 2004 John Wiley & Sons, Ltd.     

A note on the perturbation analysis for the generalized Cholesky factorization

In this note, we consider the perturbation analysis for the generalized Cholesky factorization further. The conditions for the main theorems of the paper [W.-G. Wang, J.-X. Zhao, Perturbation analysis for the generalized Cholesky factorization, Appl. Math. Comput. 147 (2004) 601-606] are weakened by using an alternative method. Moreover, some new perturbation bounds are also derived.     

Backward perturbation analysis for scaled total least‐squares problems

The scaled total least‐squares (STLS) method unifies the ordinary least‐squares (OLS), the total least‐squares (TLS), and the data least‐squares (DLS) methods. In this paper we perform a backward perturbation analysis of the STLS problem. This also unifies the backward perturbation analyses of the OLS, TLS and DLS problems. We derive an expression for an extended minimal backward error of the STLS problem. This is an asymptotically tight lower bound on the true minimal backward error. If the given approximate solution is close enough to the true STLS solution (as is the goal in practice), then the extended minimal backward error is in fact the minimal backward error. Since the extended minimal backward error is expensive to compute directly, we present a lower bound on it as well as an asymptotic estimate for it, both of which can be computed or estimated more efficiently. Our numerical examples suggest that the lower bound gives good order of magnitude approximations, while the asymptotic estimate is an excellent estimate. We show how to use our results to easily obtain the corresponding results for the OLS and DLS problems in the literature. Copyright © 2009 John Wiley & Sons, Ltd.     

A perfect one‐factorization of K52

A starter derived even starter that induces a perfect one‐factorization of K₅₂ is presented. This is the smallest order for which a perfect one‐factorization was not previously known and is the first new “small” order for which a perfect one‐factorization has been found in nearly 20 years. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 190–196, 2009     

On the modified Gram-Schmidt algorithm for weighted and constrained linear least squares problems

A framework and an algorithm for using modified Gram-Schmidt for constrained and weighted linear least squares problems is presented. It is shown that a direct implementation of a weighted modified Gram-Schmidt algorithm is unstable for heavily weighted problems. It is shown that, in most cases it is possible to get a stable algorithm by a simple modification free from any extra computational costs. In particular, it is not necessary to perform reorthogonalization.Solving the weighted and constrained linear least squares problem with the presented weighted modified Gram-Schmidt algorithm is seen to be numerically equivalent to an algorithm based on a weighted Householder-likeQR factorization applied to a slightly larger problem. This equivalence is used to explain the instability of the weighted modified Gram-Schmidt algorithm. If orthogonality, with respect to a weighted inner product, of the columns inQ is important then reorthogonalization can be used. One way of performing such reorthogonalization is described.Computational tests are given to show the main features of the algorithm.     

QR factorization of Toeplitz matrices

Summary This paper presents a new algorithm for computing theQR factorization of anm×n Toeplitz matrix inO(mn) operations. The algorithm exploits the procedure for the rank-1 modification and the fact that both principal (m–1)×(n–1) submatrices of the Toeplitz matrix are identical. An efficient parallel implementation of the algorithm is possible.     

关于酉对称矩阵的QR分解及其算法

为了简化大型行(列)酉对称矩阵的QR分解,研究了行(列)酉对称矩阵的性质,获得了一些新的结果,给出了行(列)酉对称矩阵的QR分解的公式和快速算法,它们可极大地减少行(列)酉对称矩阵的QR分解的计算量与存储量,并且不会丧失数值精度.同时推广和丰富了邹红星等(2002)的研究内容,拓宽了实际应用领域的范围.