# 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.

78 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 ...
331 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, ...
294 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 ...
380 views

### Does a symmetric positive definite matrix also have $\mathbf{A} = \mathbf{L}^T\mathbf{L}$ (where $\mathbf{L}$ is a lower triangular matrix)?

As we know, for a symmetric positive definite (SPD) matrix $\mathbf{A}$, there is a theorem about the Cholesky factorization $\mathbf{A}= \mathbf{L}\mathbf{L}^T$, where $\mathbf{L}$ is a lower ...
215 views

120 views

85 views

### Missing nonzeros in U matrix computed by SuperLU

On page 18 of SuperLU's user guide, the following sample input matrix A is given: ...
67 views

### Numerical analysis, pivoting and incomplete LU decomposition

When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
125 views

### Factorize laplacian in terms of first derivative matrix

I am trying to factorize the following Laplacian matrix in terms of $D^TD$, D is the first derivative matrix. The tridiagonal form of the secon derivative matrix using Neumann boundary condition is ...
38 views

### Reweighted least squares factorization

This is a continuation of the question asked here. I want to solve numerous least squares systems of the form $$D_i A x \approx D_i b$$ where $D_i$ are $m \times m$ diagonal matrices with positive ...
495 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 ...
135 views

### What is the computational cost of using complex numbers in contrast to real numbers in matrix operations, e.g. $LU$ or $LDL^T$ factorizations? [duplicate]

I am curious about how much one loses in terms of computational cost when complex numbers are used instead of real numbers? I guess the number of floating-point operations and memory doubles, but I ...
290 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 ...
381 views

### Fastest way to solve a sparse unsymmetric system many times

I have to solve a system $Ax^{(n)} = b^{(n)}$ many times, $A$ being a sparse (pentadiagonal in most part of its structure), unsymmetric, constant matrix. Currently, I am performing the LU ...
20k 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 ...
96 views

### Bareiss algorithm vs. LU-decomposition

I at the moment try to fully understand the Bareiss algorithm for calculating determinants. One question that came to my mind is the following: Why is LU-decomposition much more often used than the ...
837 views

### Solve Ax=B where B is a matrix in parallell

I try to solve the problem $Ax=B$ where $A$ is a large sparse $n\times n$ matrix, and $B$ is a dense $n\times m$ matrix (here $n=754850$ and $m=182$). The backslash operator yields correct solution (<...
120 views

### Re-using LU factorization within iterative (?) setup for a sum of two matrices

So, I would love to make at least some use of my preexisting data, no matter how small, and just out of ideas. Maybe I am just a prisoner of a Kahneman-like theatre-ticket paradox, and don't know ...
324 views

### How we can use CUR decomposition in place of SVD decomposition?

I have understood how CUR and SVD works, but have not been able to understand the following. How can we use CUR in place of the SVD decomposition? Do the $C$ and $R$ matrices in the CUR follow the ...
143 views

### Converting matrices L and U output by dgssv() of SuperLU to triples format

How can I convert matrices L and U output by dgssvx() of SuperLU to triples format (to ...
137 views

### Givens rotation vs 2x2 Householder reflection

The usual story of Givens rotations vs Householder reflections is that Householder reflections are better if you want to map a long vector to $e_1$, while Givens is better if you want to map a 2-...
122 views

### Regularized least squares with QR factorization

Consider the regularized least squares problem $$\min_x || b - A x ||^2 + \lambda^2 ||x||^2$$ which is equivalent to  \min_x \left|\left| \pmatrix{b \\ 0} - \pmatrix{A \\ \lambda I} x \right|\...
36 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 ...
744 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 ...
91 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-...