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
3 votes
0 answers
84 views

Eliminate variables from a large system of equations

I have a large system of equations $Ax=0$. For context, the equations are invariants of some model. $A$ is sparse and typically has more columns than rows ($m < n$). The $x$ vector can be divided ...
io6nZ's user avatar
  • 31
1 vote
0 answers
56 views

SVD decomposition and the update problem of matrix differential equations

For a matrix $Y(t) \in \mathbb{R}^{m \times n}$, its rank-r approximation could be represented in a factorized SVD-like form. $$ Y(t) = U(t) S(t) V^T(t), $$ where $U^{T}U = I_m$, $V^{T}V = I_n$ and $S ...
Owen Jun's user avatar
  • 141
0 votes
0 answers
60 views

Singular Matrix Error in Incomplete LU Decomposition

I’m currently working on solving the following PDE: $$\begin{equation} -(\mu_x \frac{\partial^2 u}{\partial x^2} + \mu_y \frac{\partial^2 u}{\partial y^2}) = f(x, y)\end{equation}$$ Where a right hand ...
blov's user avatar
  • 43
1 vote
2 answers
101 views

Implementing matrix term version of Gauss-seidel

I am trying to implement the below description from Ch. 11 of Heath's "Scientific Computing An Introductory Survey" of the Gauss-Seidel iterative method for solving a system of linear ...
Jared Frazier's user avatar
1 vote
1 answer
89 views

enough conditions to check that a matrix doesn't have Cholesky factorization while factorizing it

I wrote this code to find Cholesky factorization of a symmetric positive definite matrix in MatLab: ...
Ferran Gonzalez's user avatar
2 votes
0 answers
67 views

Efficient Algorithm for LU-Factorization of Modified Matrix with Last Column Alteration If We Have Its Not-Modified LU-Factorization

Suppose that we have a $n\times n$ matrix $A$. We have its LU-factorization as $A=LU$ (or $PA=LU$ that $P$ is a permutation matrix). Now assume we change the last column of matrix $A$ and denote the ...
Ferran Gonzalez's user avatar
0 votes
0 answers
211 views

Right blocked linear equation solver on Dense Algebra and Sparse Algebra

I have implemented 1D mesh parallel QR decomposition and LU decomposition,I would like to ask if a linear equation Ax=b,b is a large matrix and I need to shard b or Shard A,b at the same time. Is ...
Haitao Xiao's user avatar
4 votes
1 answer
331 views

How to efficient solve $e^{-tA} x =b$, where A is a very sparse matrix

I am going to solve an equation containing an exponential matrix $e^{tA} x =b$, which can be obtained naturally through $x=e^{-tA} b$. A is a 1million $\times$ 1 million matrix with stores 7.15 ...
Owen Jun's user avatar
  • 141
0 votes
1 answer
99 views

row and column based distributed LU factorization

The LU parallel computation theories I've seen are based on $M\times N$ mesh computations, is there a theory for one dimensional device mesh LU parallel decomposition? For example, $A$ is a matrix. we ...
Haitao Xiao's user avatar
4 votes
2 answers
242 views

Reordering eigenvalues in Schur factorization - MATLAB ordschur 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
108 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
159 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
162 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
124 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
  • 265
2 votes
0 answers
133 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
268 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
2 votes
0 answers
35 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
120 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
71 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
137 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
52 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
93 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
508 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
57 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
  • 767
3 votes
0 answers
68 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
  • 607
1 vote
1 answer
105 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
1k 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
551 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
  • 2,112
1 vote
1 answer
986 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 ...
user avatar
5 votes
2 answers
588 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
259 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
153 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
60 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
151 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
  • 934
4 votes
2 answers
285 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
68 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
  • 445
0 votes
1 answer
151 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
449 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
231 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
147 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
402 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
  • 297
2 votes
0 answers
73 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
  • 445
1 vote
1 answer
314 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
75 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
2 votes
2 answers
471 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
270 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
373 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
55 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
516 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