We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [matrix-factorization]

Decomposition of a matrix into a product of matrices with special properties. Common matrix factorizations include LU, QR, SVD, and Cholesky.

66 questions
Filter by
Sorted by
Tagged with
7k views

### Robust algorithm for $2 \times 2$ SVD

What is a simple algorithm for computing the SVD of $2 \times 2$ matrices? Ideally, I'd like a numerically robust algorithm, but I'll like to see both simple and not-so-simple implementations. C code ...
273 views

### Rapidly determining whether or not a dense matrix is of low rank

In a software project that I'm working on, certain computations are vastly easier for dense low-rank matrices. Some problem instances involve dense low-rank matrices, but they're given to me in full, ...
242 views

### The fast, and The Backward-Stable (left) $3\times 3$ matrix inverse

I need to compute a lot of $3\times3$ matrix inverses (for Newton iteration polar decomposition), with very small number of degenerate cases ($<0.1\%$). Explicit inverse (via matrix minors divided ...
198 views

349 views

### Existence of incomplete cholesky factorization

What is the current state of research on the existence of incomplete cholesky factorizations (in the context of preconditioning) for symmetric positive definite matrices? I wonder in particular ...
88 views

### Is the bandwidth of indefinite A equal to its factor L in LDL^T?

In George, Liu, and Ng's book Computer Solutions of Sparse Linear Systems, it has been shown that bandwidth of $A$ is equal to bandwidth of its factors in $LL^T$.(section 4.3) However, I guess this is ...
145 views

### Rank-one Update to a Rank Revealing QR (RRQR) Factorization?

Suppose we are given an RRQR factorization for some matrix $A \in \mathbb{R}^{m \times n}$, $A\Pi = QR$ where $m > n$. Is there a cheap way to update $A' = A + uv^{\top}$ given this factorization?...
126 views

### Numerically find the nearest positive semi definite matrix to a symmetric matrix

I have a symmetric matrix $M$ which I want to numerically project onto the positive semi definite cone. To do so, I decompose it into $M = QDQ^T$ and transform all negative eigenvalues to zero. (...
101 views

### Term for the typical “linear in the larger dimension, quadratic in the smaller” cost for linear algebra

Many dense linear algebra decompositions (QR, SVD...) on an $m\times n$ matrix have cost $$O(\max(m,n)\min(m,n)^2)$$ when implemented in practice on a computer. Is there a colloquial name or a more ...
96 views

### Do most statistical packages and libraries in high-level programming languages rely on LAPACK for their matrix inversion operations?

Possible an open-ended question, but I am wondering if most statistical packages and libraries, for instance, Stata, R, Python's NumPy and MATLAB rely on LAPACK algorithms to perform matrix operations,...
97 views

### Does $\log(\det(A))$ equals sum of log of diagonal elements of D in LDLT decomposition?

For a large matrix $A$, I need to evaluate the $\log(\det(A))$. I already have it's LDLT decomposition. Is it possible to evaluate the $\log\det$ with the elements of the diagonal $D$ of the LDLT ...
384 views

### Code to update dense QR and Cholesky factorizations

I am looking for some production-ready code to update dense QR and/or Cholesky factorizations (by adding / removing rows and columns or making small-rank updates -- yes, I need all these cases). I ...
86 views

### Is there an efficient $O(n^2)$ way to get the eigen decomposition given a LDL factorization?

Let's say I have a LDL factorization of a matrix A. Is there an efficient $O(n^2)$ way to get the eigen decomposition of A given it's LDL factorization? Is there a more efficient way, in case L and ...
34 views

### Low rank update of QR of inverse

I am in a situation where as part of a sort of inverse power method scheme, I want to very often perform the following step: Apply a symmetric rank one update $uu^\top$ to my inverse matrix $A^{-1}$ ...
119 views

### Inverting a matrix from LU decomposition

The LAPACK routines xGETRI compute the inverse of a matrix $A = PLU$ in its LU decomposed form by first computing $U^{-1}$, and then solving the system: $$(A^{-1} P) L = U^{-1}$$ My question is: ...
154 views

### Factorization for reweighted least squares

I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Essentially this requires solving a number of least-...
125 views

### Factoring the sum of two matrices

Given \begin{equation} A_i=B+C_i \end{equation} where $A_i$,$B$ and $C_i$, $i=1,\dotsc,N$ are large square matrices, $B$ is symmetric, $C_i$ are zero matrices aside for a square block on the diagonal. ...
52 views

### Weighted QR Implementation

Say I want a QR decomposition of matrix $A$, where orthogonality of $Q$ is with respect to a generic non-degenerate positive-definite bilinear form $\phi$ (in my case, $\phi$ is "defined" by a finite-...
319 views

### Solve rank one update to LU using plain vanilla LU routine

I have a large number of systems of the form: $$A_ix=b,$$ where each $A_i,i>0$ is a rank one update of $A_{i-1}$ and the $A_i$ are dense matrices. I was wondering whether it is possible to use the ...
249 views

29 views

### ILUTP in sparse.linalg.spilu?

In Matlab, an ILU with threshold and pivoting (ILUTP) can be passed by default as: setup.type = 'ilutp'; [L, U] = ilu(A, setup); Looking for an equivalent in ...
440 views

### Difference between fast and normal Givens Rotations?

would someone be so kind as to explain me the difference between the ordinary givens-rotation and the fast givens-rotation? I know that the fast givens Rotation reduces the Count of operations to ...
457 views

### Ways to solve $Ax=b$ for a sparse (banded) $A$ with updates

I want to solve the time-dependent Schrodinger Equation using the Crank-Nicolson scheme. I end up with the following matrix equation ...
90 views

### What is the cost of factorization for one-dimensional sparse problems?

In Golub and Van Loan's book, Matrix Computations, page 606, it is stated that: With standard discretizations, 2-dimensional problems can be solved with $O(n^{3/2})$ work and $O(n \log{n})$ fill-...
125 views

### Cholesky for ill-conditioned/singular covariance matrices

Can someone suggest a way to get Cholesky factorization of a singular covariance matrix? I need it to match Cholesky on full-rank matrices, ie coordinate order should be preserved. My attempt below ...
135 views

### Supernodal vs multifrontal factorizations

What are the differences between supernodal and multifrontal matrix factorizations? Can you provide a few references or high-level points about the approaches?
59 views

### Classical vs. modified Gram-Schmidt

It is often said that modified Gram-Schmidt is more robust with respect to rounding errors than classical Gram-Schmidt, but it is very hard to find a good explanation / example of why this is so. Can ...
171 views

### numerically stable routines to compute $M = B A^{-1} B$

Rather than gesv -> solve $AX = B$ gemm -> compute $M = BX$, somehow I feel there are better ways to compute $M$ with lapack/mkl?
18k views

### why Lapack routine dgesv doesn't solve this?

Suppose I have the following 3 by 3 matrix: p<-3 X<-matrix(1/p,p,p) --$\pmb X$ is just a $p$ by $p$ matrix where every entry is $1/p$. Now I want to solve ...
44 views

### Incomplete LU decomposition of sparse matrix

I have a sparse matrix stored in CSR format. For this matrix, I would like to get the incomplete LU decomposition. I tried to find algorithms which can utilize the CSR format but I could not find ...
47 views

### How to use QZ decomposition for single matrix in Matlab?

Can I use QZ decomposition on a single square matrix in Matlab? Like, [Aa,Q,Z]=qz(A);
452 views

### Clever ways to update LU factorization for ridge regression

Ridge regression can be posed as minimizing the following objective function (over $x$): $$\frac{1}{2} \lVert Ax - b \lVert_2^2 ~+ \frac{\lambda}{2} \lVert x \lVert_2^2$$ Which has a closed form ...
Assume I have a sequence of vectors $v_k \in V$ in some abstract vector space $V$ not necessarily equal to $\mathbb{C}^n$. Can I still use the Householder QR decomposition in this case, even though ...