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.

Filter by
Sorted by
Tagged with
2 votes
2 answers
167 views

Reordering eigenvalues in Schur factorization - MATLAB orschur and LAPACK dtrsen not producing the same results

Disclaimer: I previously posted this on SO, but though it would be more relevant for scicomp. The original post has been deleted. I have been trying to recreate the functionality provided by MATLABs <...
two_Thomas's user avatar
1 vote
1 answer
63 views

Calculating camera calibration matrix with Scilab

I'm not entirely sure whether this question belongs here or in DSP but I think this is the proper site. I'm following these videos (first video, second video) to calibrate a camera for photogrammetry ...
Vaahterasiirappi's user avatar
4 votes
1 answer
132 views

Is there a way to generate a matrix-free decomposition for a matrix-free operator?

Hypothetical question for some code that I'm writing. Suppose I have an matrix-free linear operator $A$, i.e. the only thing I know about it is the forward action $v \mapsto Av$. For simplicity, let's ...
TrostAft's user avatar
  • 141
4 votes
1 answer
112 views

The error propagation in calculating the inverse using a matrix decomposition

I have been trying to calculate the matrix inverse of some large matrix with entries ranging by orders of magnitude. I tried to use the matrix decomposition to simplify the computation, where a matrix ...
ShoutOutAndCalculate's user avatar
2 votes
0 answers
108 views

Is the Hessian of the strain energy of a hyperelastic material positive definite in general

Is the spatial second derivative of the strain energy of a hyperelastic material positive definite in general? If this is not a general property of hyperelastic materials are there techniques for ...
Olumide's user avatar
  • 255
2 votes
0 answers
130 views

Does exact diagonalization of a matrix allow for efficient computation of a Lanczos basis?

Suppose that we are given a large, real-symmetric matrix $L$, which is simply too large to perform exact diagonalization on numerically. If we want to study its spectrum, one tool we can use is the ...
miggle's user avatar
  • 41
5 votes
1 answer
167 views

Block-Tridiagonal Matrices with tridiagonal blocks

The Setup Using finite differences to discretize the 2d diffusion equation $$\partial_tu=\partial_x\left(A\partial_xu+B\partial_yu\right)+\partial_y\left(B\partial_xu+C\partial_yu\right)$$ we get a ...
Michael's user avatar
  • 153
0 votes
0 answers
17 views

Nimfa Lsnmf matrix factorization with sparse input: wrong/different result than dense input

I just started using Nimfa and working on a dummy example. I would like to do a matrix factorization (on a matrix for which we do not have all the entries) and I am assuming the following model (which ...
Bob.S.P's user avatar
2 votes
0 answers
34 views

How to exploit QR factorization implicitly

I meet a problem when I try to develop an iterative method for discrete inverse problem $$Ax+e=b$$ where $A\in\mathbb{R}^{m\times n}$ and $e$ is a noise. I want to approximate the true solution $x_{...
Haibolee's user avatar
1 vote
0 answers
89 views

What's the best modern algorithm for recursive least squares?

Recursive least squares can be implemented using the Sherman–Morrison formula to avoid resolving, however, have better methods without $n^2$ cost been developed? I'm interested if there is a good ...
Torkoal's user avatar
  • 111
1 vote
1 answer
70 views

Efficient and stable QR factorization of partially orthonormal matrix

Let $U \in \mathbb{C}^{m \times n_U}$ be an orthonormal matrix, let $A \in \mathbb{C}^{m \times n_A}$, and $m \geq n_U + n_A$. I want to compute a QR factorization $X = \left[U A\right] = QR$, with $Q ...
coolguy1000000's user avatar
1 vote
1 answer
92 views

QR decomposition with only diagonal elements changing

I have to compute the QR decomposition of a matrix A repeatedly, each time with ONLY diagonal elements changing. Is there an efficient way to accomplish this ...
Madhurjya's user avatar
  • 111
2 votes
0 answers
51 views

Finding spectrum of a Kronecker factored + block-partitioned matrix

I have dense $d\times d$ matrices $A$, $B$, $C$ with $d\approx 1000$ and want to find the top $10^5$ eigenvalues of the following positive definite matrix: $$ \Sigma= \left(\begin{matrix} A\otimes A &...
Yaroslav Bulatov's user avatar
0 votes
1 answer
91 views

Diagonalization of factored matrix

I have a matrix $X=CC^T$ that I want to diagonalize. Here $C$ is a known $n\times n$ matrix, which I could also factor as $LM$ if it helps, $L$ being a lower triangular matrix and $M$ another matrix. ...
PC1's user avatar
  • 436
1 vote
2 answers
456 views

Solution to Sylvester-like equation

I have an equation that is a bit similar to a Sylvester equation. The equations is $AXB^T+X=E$, where all variables are matrices. I could try to inverse $B$ and rewrite the equation as $AX+XB^{-T}=EB^{...
PC1's user avatar
  • 436
2 votes
0 answers
48 views

Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R?

Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R to the end of the diagonal? As an example, consider the following snippet of MATLAB ...
wyer33's user avatar
  • 747
3 votes
0 answers
63 views

Dense factorization specialized for RBF-FD method

In RBF-FD methods (see Fornberg & Flyer. A Primer on Radial Basis Functions with Application to the Geosciences. SIAM, 2015. Chapter 5.), the finite-difference stencil coefficients for a set of ...
IPribec's user avatar
  • 452
1 vote
1 answer
96 views

Fast algorithm to compute chi-square

I would like to evaluate the chi-square of the form $\chi^2=v^{T}C^{-1}v$ where $v$ is a column vector and $C$ is a covariance matrix. Both $v$ and $C$ are known and $C$ is a $740\times740$ matrix. ...
user7896's user avatar
  • 123
0 votes
2 answers
634 views

Incomplete Cholesky factorization algorithm

I want to implement incomplete Cholesky factorization to precondition, the algorithm I refer from incomplete Cholesky factorization, ...
TiantianHe's user avatar
3 votes
1 answer
395 views

Incomplete Cholesky preconditioner for CG efficiency

I am currently solving the harmonic equation using a P1 FEM discretisation. The resulting matrix $A$ is SPD and fairly sparse so I use a preconditioned conjugate gradients (CG) solver to find a ...
lightxbulb's user avatar
1 vote
1 answer
842 views

Givens rotation algorithm without matrix-matrix multiplication

I would like to implement a givenRotation algorithm without having matrix-matrix multiplication. Matrix-vector is fine or just for looping. I am to decompose a rectangular (m+1)xm Hessenberg matrix. I ...
Manuel Oliveira's user avatar
5 votes
2 answers
580 views

Computational method to compute both the (log) determinant and inverse of a matrix

Suppose I have a square matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$ and a vector $\mathbf{b}\in\mathbb{R}^n$. In my application I need to accomplish two things. I need to find the solution of the ...
5d41402abc4's user avatar
6 votes
1 answer
240 views

Algorithm for solving systems which are nearly symmetric/adjoint?

I am familiar with Cholesky decomposition and LU factorization for solving systems of linear equations. I have a problem where I have large sparse matrices (say, 1000x1000 or larger) where only one or ...
user3814483's user avatar
3 votes
0 answers
135 views

Invert a huge sparse operator;

please help me with this question, I want to invert a huge sparse (non-circulant) this below in a $Ax=y$ equation: $$(\lambda I+ \beta D+ \sigma C)x=y$$ where I is an Identity Matrix,D is a Diagonal ...
Vy Trieu's user avatar
1 vote
0 answers
55 views

Using the lower triangular portion of a matrix to return a Symmetric Positive Definite Matrix?

I've recently posted this question. To summarise, I'm dealing with supposedly Symmetric Positive Definite(SPD) matrices, but due to machine-precision they end up not being SPD. In a comment, a user ...
An old man in the sea.'s user avatar
3 votes
2 answers
139 views

Efficient schemes for solving the extended Saddle point problem

I am interested in knowing some efficient techniques for solving the following extended Saddle point problem. \begin{align} \begin{bmatrix} A & B^T & C^T \\ B & 0 & 0 \\ C & ...
Chenna K's user avatar
  • 865
4 votes
2 answers
243 views

Is there a simple way to add a sparse matrix to an LU decomposition of a dense matrix?

I am solving a parabolic equation in the form: $$ \left( {M \over\tau_j} + A \right) u^{j+1} = M f^j + {u^j \over \tau_j}, $$ where $A$ and $f$ are a dense stiffness matrix and the right hand side of ...
Dimitar Slavchev's user avatar
8 votes
3 answers
1k views

Accurate Way to Calculate Matrix Powers and Matrix Exponential for Sparse Positive Semidefinite Matrices

I do need to numerically calculate the following forms for any $x\in\mathbb{R}^n$, possibly in python: $x^T M^k x$, where $M\in\mathbb{R^{n\times n}}$ is a PSD sparse matrix, $n$ can be quite large ...
Cupitor's user avatar
  • 183
1 vote
0 answers
59 views

Nonsymmetric permutations for LU factorisation of symmetric matrix

Let $A$ be a symmetric matrix. It is then well known that computing the LU factorisation of $PAP^T$ instead of $A$ for a suitably chosen permutation matrix $P$ can greatly reduce fill-in. My question ...
gTcV's user avatar
  • 425
0 votes
1 answer
137 views

Solve for large array of PD matrices

I have N matrices that are positive definite, and I have to solve for a M vectors. As M is large in my case, doing all solves simultaneously using np.linalg.solve ...
Yiftach's user avatar
  • 109
3 votes
1 answer
371 views

Quick way to find a common basis of eigenvectors between 2 matrices : valid or not?

Following the advise of @Federico Polonion a previous post, one suggested, to find a basis of common eigen vectors between 2 matrices, to simply do : Generate 2 ...
user avatar
2 votes
1 answer
196 views

Efficiently compute a projection matrix from Householders reflectors

Let $A \in \mathbb{R}^{m \times n}$ where $m \geq n$. Let $B$ and $\tau$ be the result of applying LAPACK's dgeqrfp method (R on the upper right triangle, and the ...
Matthias Beaupère's user avatar
1 vote
2 answers
142 views

Solving a specific sparse linear system without dense materialization

I need to (computationally) solve a system of equations, for the purposes of an interior point method, of the form $$ \left[\begin{array}{cc}B & A^T \\ A & 0\end{array}\right] \left[\begin{...
ckfinite's user avatar
  • 113
2 votes
1 answer
358 views

Numerical Linear Algebra: When to use Direct methods versus iterative methods to solve a linear system - for PDEs in particular

I am reading the Chapra and Canale book on numerical methods, and was working through the chapters on solving linear systems. Now the book goes through direct methods including Gaussian Elimination, ...
krishnab's user avatar
  • 287
2 votes
0 answers
72 views

Does incomplete LU preconditioning improve the asymptotic scaling of Krylov subspace methods?

It is well known that unpreconditioned Krylov subspace methods applied to the finite-difference-discretised Poisson equation with $n$ grid points per direction require $O(n \, |\log(\varepsilon)|)$ ...
gTcV's user avatar
  • 425
1 vote
1 answer
290 views

Range of a matrix from its complete orthogonal decomposition

In this StackOverflow answer, @Gokul has shown how to get a basis of the kernel of a matrix with the help of the 'Eigen' function CompleteOrthogonalDecomposition. ...
Stéphane Laurent's user avatar
4 votes
0 answers
74 views

Efficient computation of marginalized multivariate normal likelihood

In general,if we know that the marginal Gaussian distribution for some variable $\textbf{x}$ and a conditional Gaussian distribution for some $\textbf{y}|\textbf{x}$ of the forms: $$p(\textbf{x}) = \...
nwknoblauch's user avatar
0 votes
2 answers
376 views

"WY" representation of QR factorization -- implementations?

I have a matrix $A \in \mathbb{R}^{m \times n}$ where $m \gg n$ and I want to compute the full QR decomposition $A = QR$. Where $Q$ is an orthogonal $m \times m$ matrix. Bishof & Van Loan (1987) ...
digbyterrell's user avatar
2 votes
1 answer
251 views

Methods to improve the efficiency and the memory requirement of LU factorization for complex symmetric system matrix

I want to solve a linear set of equations (Ax=b) using LU decomposition. My "A" matrix is a complex matrix which is ...
HKK's user avatar
  • 33
2 votes
0 answers
304 views

Computing Singular Value Decomposition of small ($4\times 4$) matrices

I need to compute the Singular Value Decomposition (SVD) of many $4 \times 4$ matrices. I'm looking for SVD algorithms specialized for small matrices. I've read that the ...
mana's user avatar
  • 131
1 vote
0 answers
54 views

Binary data clustering by Matrix factorization [closed]

I have read an article talking about binary clustering using Matrix factorization(see attached), but i would like to understand some optimization concepts: Is it reasonable to use a Frobenius norm in ...
user36820's user avatar
1 vote
1 answer
478 views

Implementation of sparse matrix SVD for GPU

I have a sparse matrix $W$ which is almost-squared ($N+1 \times N$) and I would like to know the eigenvalues of $A = W^T W$. $A$ is Hermitian so the eigenvalues are real-positive valued. The usual ...
simone's user avatar
  • 11
1 vote
1 answer
251 views

Efficient way to solve a set of linear equations $Ax=b$ when $A$ is sparse and some elements of $b$ are equal to zero

I have a set of linear equations, $Ax=b$. And about half of the elements in the right-hand side (vector $b$) are equal to zero. My system matrix $A$ is a sparse complex matrix. And $A$ is in the size ...
HKK's user avatar
  • 33
1 vote
1 answer
184 views

Functions from Scipy, Blas, or Lapack that compute only upper triangular matrix

My goal is to transform a matrix into upper triangular form in Python. I know the function scipy.linalg.lu will do LU decomposition and get both upper and lower ...
Akira's user avatar
  • 207
3 votes
1 answer
1k views

Why is 'scipy.sparse.linalg.spilu' less efficient than 'scipy.linalg.lu' for sparse matrix?

I have a matrix B which is sparse and try to utilize a function scipy.sparse.linalg.spilu specialized for sparse matrix to ...
Akira's user avatar
  • 207
5 votes
1 answer
184 views

Algorithm to factorize matrix whose many rows are already of upper triangular form?

I have a matrix whose many rows are already in the upper triangular form. $$\begin{bmatrix} x_{11} & x_{12} & x_{13} & x_{14} & x_{5} \\ 0 & x_{22} & x_{23} & x_{...
Akira's user avatar
  • 207
1 vote
0 answers
47 views

Triangle on top of diagonal least squares

I need to solve many least squares problems with the following matrices: $$ \pmatrix{ R \\ D_i } $$ where $R$ is upper triangular and $D_i$ is diagonal. $R$ is the same for all the problems, while $...
vibe's user avatar
  • 1,038
0 votes
2 answers
386 views

Reorder eigenvalues in Schur factorization in descending order

In this command: [US,TS] = ordschur(U,T,select) what should replace the select to rearrange the eigenvalues in descending ...
Jake's user avatar
  • 41
1 vote
1 answer
256 views

How can I get Cholesky decomposition from eigenvalue decomposition?

I have $$S = QLQ^T$$ I know $Q$, $L$, $Q^T$. How can I get the $R$ and $R^T$ for the Cholesky decomposition $S=R^TR$?
Jing Bai's user avatar
3 votes
2 answers
354 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 ...
user avatar