# Questions tagged [sparse-matrices]

Use this tag for questions regarding sparse matrices, that is matrices with relatively few entries compared to their size. Related: [numerical-methods] and [numerical-linear-algebra].

193 questions
Filter by
Sorted by
Tagged with
27 views

### How to maximize the sparsity of orthogonal matrix?

Given a unit vector $v\in\mathbb{R}^n$, it's needed to find an orthogonal matrix $Q\in \mathbb{R}^{n\times m}$ ($m \leq n$) of maximum sparsity. What are the bounds of sparsity for such matrix? What ...
• 834
45 views

35 views

• 1,249
53 views

### Is the product $B D B^T$ always a symmetric tridiagonal matrix? Where $D$ is a diagonal matrix and $B$ a sparse matrix.

I have a diagonal matrix ${\bf D}_{n \times n}$ and a rectangular matrix ${\bf B}_{m \times n}$ where $n \gg m$. All but $m$ rows of ${\bf B}$ have non-zero elements. These $m$ rows have only six non-...
• 1,249
37 views

### Inverse of a special hermitian sparse matrix

While exploring some data modelling, I observed without being able to prove it that the inverse of matrix $A$ of the following form: it is hermitian, i.e. $A_{ij}=A^{*}_{ji}$ it has non-zero positive ...
65 views

### Eigenvalue decomposition for $A^TA$ for sparse A?

I have a sparse matrix $A \in \mathbb{R}^{n \times l^{2}}$, and I want to calculate the eigenvalue decomposition of $A^{\top}A$. Since $A^{\top}A$ is positive semidefinite, all the eigenvalues are non-...
• 1,666
106 views

### What is computationally the fastest way to calculate $\mathrm{Tr}(A^n)$ and $\mathrm{Tr}(A^{n-1}B)$?

Let $A \in \mathbb{R}^{N\times N}$ be a large symmetric matrix that has at most $\frac{1}{8}$ of its elements non-zero. We have an equation that involves a term $\mathrm{Tr}(A^n)$, that is, trace of ...
12 views

### how to solve the reweighted Poisson equation efficiently

Consider the following reweighted Poisson equation: given $\operatorname{Q}$ and $g$, $$(\nabla \cdot \operatorname{Q} \nabla ) f = g,$$ where $\operatorname{Q}$ is a diagonal matrix with ...
77 views

### Steady state in CFD: Solving large and sparse linear equation of the form $Ax =b$.

In CFD and computational physics a space can be discretized by describing it as a large amount of tiny volumes or cells. To find a steady state in the scheme, for example solving the electric field ...
331 views

### Sparse Cholesky decomposition of factorized matrix

I want the diagonal of a matrix $Y^TA^{-1}Y$ where $A=X^TX$ and $X$ is very sparse with dimensions ~1e6 x ~1e5 (so $A$ is 1e5 by 1e5). $Y$ is something like 1e5 by 1e4 (also sparse). Currently I'm ...
• 153
64 views

### How to fit/pack a graph into a $2D$ grid without destroying the connectivity?

Given a graph like the one below, I try to pack/fit this graph into a fixed row $2D$ grid and use as few columns as possible. I can change the shape of the graph, but not the connectivity. For example,...
• 11
406 views

### Best algorithm to solve a large linear system (from discretization of high-dimensional PDE) with coefficient matrix very sparse, banded, known shape

I want to solve a large system of linear equations $A x = b$ that derives from the discretization of a PDE in a high dimensional space. For now, I have $3$ dimensions but I will eventually increase ...
• 41
1 vote
96 views

### Random sparse positive semi-definite matrix

I would like to generate random covariance matrices with the constraint that only particular pairs of variables are correlated. A covariance matrix is a positive semi-definite matrix. Given a set of ...
• 203
60 views

### When is the inverse of a sparse SPD matrix also sparse?

I have seen in several places that the inverse of a sparse matrix is generally not sparse, but I have failed to find more in-depth analysis than empirical or case-by-case studies. My question is the ...
69 views

### Is there an efficient way to solve a system of linear equations with an almost tridiagonal sparse matrix?

I have a problem where I need to solve a linear system of equation $Ax = b$ where the matrix A is almost tridiagonal, except for elements on the last two columns (see below). I need to solve such a ...
• 71
42 views

### Inverse of a matrix with sparse rows and columns.

I understand the inverse of a sparse matrix is not necessarily sparse; however, I was wondering if there is anything to be said about the inverse of a matrix with a constant number of 1s in each of ...
• 964
355 views

Suppose $$A = \begin{pmatrix}0&0&-1&&&\\ 1&0&0&-1&\ddots\\ &\ddots&\ddots&\ddots&\ddots\\ &&1&0&0&-1\\ &&&1&0&... • 5,002 1 vote 1 answer 82 views ### Min. Number of Sparse Matrix Elements to preserve Matrix Properties under Permutations Given matrices S \in \mathbb{R}^{G \times K}, Q\in \mathbb{R}^{K \times K} and T \in \mathbb{R}^{G \times K} with T = S \cdot Q, I would like to find the minimum number of sparse elements in ... • 61 1 vote 0 answers 59 views ### When are LU factors of sparse matrices surely sparse? The other week I revisited an old classic factorization from my bachelors studies, the LU-factorization. The LU factorization of a (square) matrix M finds lower and upper triangular matrices (L and U ... • 26k 1 vote 0 answers 31 views ### Calculating specific rows of sparse linear system solution I have a large linear system AX = B given by sparse matrices with A,X,B being large matrices of size n\times n, n\times m, n\times m respectively. Both A and B are sparse matrices and n\gg ... 2 votes 0 answers 55 views ### Eigendecomposition of a block tridiagonal matrix Is there an efficient way to diagonalize a block tridiagonal N\times N matrix of the following form: \begin{matrix} A_0 & B & 0 & 0 & \ldots \\ B & A_1 & B & 0 & \... 0 votes 0 answers 51 views ### Flattened Sparse Matrix vs Function Notation For Research Papers I am currently working on writing a report for my research project, which involves flattened sparse matrices in the mathematics. Basically, I have multi-dimensional tensors of the form  D \in \mathbb{... • 131 1 vote 0 answers 52 views ### Solve for closest sparse upper-triangular matrix given lower-triangular matrix and tridiagonal matrix I have a sparse lower triangular square matrix L. This is the Cholesky factor or the R matrix from QR decomposition of a symmetric tridiagonal matrix H_1. Since L is the Cholesky factor of a ... • 11 0 votes 0 answers 164 views ### Help understanding the solver used in scipy spsolve and why its result is usually sparse In scipy.sparse.linalg package there is a solver called spsolve that solves$$ AX = b $$where A,b are a sparse matrices. ... • 1 3 votes 2 answers 261 views ### Eigenvalues of a sparse 8x8 matrix I have the following  8 \times 8  sparse matrix  P=\begin{bmatrix} 0.5 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.5 & 0.5 & 0.0 & 0.... • 434 2 votes 1 answer 524 views ### Inverse of matrix with hadamard product Let A and B, X be matrices with \mathbb{R}^{n \times n} where A, B are a dense and sparse matrix, i.e., the almost elements of B are zeros, respectively. I'm looking for a way to solve ... • 21 1 vote 2 answers 412 views ### Inverting a huge sparse banded matrix I have a matrix of 9,200 \times 9,200 elements. I have approximately 90 of these matrices to invert. The reason for this is I am running a nonlinear regression on a problem with significant errors ... 2 votes 2 answers 264 views ### Inverse of a particular sparse matrix I need to find the inverse of a sparse square matrix that has the following sparsity pattern.$$\begin{bmatrix} * & * & * & * & * & * & * & * \\ * & * & 0 & 0 &...
• 159
Problem definition Given an integer $N>1$, let $A_N$ be the following $N\times N$ matrix \begin{equation*}A_N\triangleq \left[\begin{array}{c|c} & I_{N-1} \\ \hline 0_1 & \end{array}\...