Skip to main content

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
Rusurano's user avatar
  • 834
0 votes
1 answer
45 views

Solving $Ax=b$: Projection onto subspace with a canonical basis of largest error

The goal is to solve the linear system $Ax = b$, where $A$ is symmetric and positive definite (SPD). Consider the one-dimensional projection method given by equation (1): $$x_{k+1} = \operatorname{...
Meow's user avatar
  • 165
0 votes
0 answers
30 views

A sparse matrix set where a matrix and its inverse share the identical sparse structure.

Define a sparse matrix set where a matrix and its inverse have the same sparse structure. Is such a set forming a certain group? For example, $\begin{bmatrix}a & b\\0 & c \end{bmatrix}^{-1}=\...
fibon's user avatar
  • 123
0 votes
0 answers
59 views

Decide whether a 0-1 matrix has full rank

Is there a theorem about when a (sparse) 0-1 matrix $A = (a_{ij})_{\substack{1\leq i\leq n\\ 1\leq j\leq m}}$ has full rank? More concretely, I know the row sums of $A$, $$ r_i = \sum\limits_{j=1}^m ...
mathaholic's user avatar
0 votes
0 answers
35 views

Sparse NMF multiplicative update rules with zero-rows in coefficient matrix

I am working with Nonnegative Matrix Factorization, where I factor a nonnegative matrix $\mathbf{X}$ into a basis matrix, $\mathbf{W}$ and a coefficient matrix, $\mathbf{H}$. $$\mathbf{X}\approx \...
madsnibe's user avatar
0 votes
1 answer
45 views

Can a sparse linear system be simplifed by dropping zero-valued rows and columns

I am solving a problem in which, the product of the transpose of a sparse matrix $M^T$ and the matrix $M$ is a large, sparse square matrix having the form: $$ \begin{array}{ccccccccc} 1\; & 2\; &...
Olumide's user avatar
  • 1,249
0 votes
0 answers
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-...
Olumide's user avatar
  • 1,249
0 votes
0 answers
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 ...
Riccardo Buscicchio's user avatar
0 votes
0 answers
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-...
wsz_fantasy's user avatar
  • 1,666
2 votes
0 answers
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 ...
Marabellum's user avatar
0 votes
0 answers
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 ...
Xue Feng's user avatar
0 votes
0 answers
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 ...
Magemathician's user avatar
5 votes
1 answer
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 ...
daknowles's user avatar
  • 153
0 votes
0 answers
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,...
Amanli's user avatar
  • 11
3 votes
0 answers
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 ...
François's user avatar
1 vote
1 answer
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 ...
Nichola's user avatar
  • 203
2 votes
0 answers
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 ...
Janjounoux's user avatar
5 votes
1 answer
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 ...
Benji's user avatar
  • 71
0 votes
2 answers
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 ...
atul ganju's user avatar
0 votes
1 answer
355 views

Determinant of a sparse matrix.

Suppose $$A = \begin{pmatrix}0&0&-1&&&\\ 1&0&0&-1&\ddots\\ &\ddots&\ddots&\ddots&\ddots\\ &&1&0&0&-1\\ &&&1&0&...
BAYMAX's user avatar
  • 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 $...
N8_Coder's user avatar
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 ...
mathreadler's user avatar
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 ...
Oscar Lazo's user avatar
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 & \...
Ritteraxt's user avatar
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{...
Han's user avatar
  • 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 ...
agoudar's user avatar
  • 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. ...
Arun's user avatar
  • 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....
Tomer's user avatar
  • 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 ...
Wanny's user avatar
  • 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 ...
George Gayton's user avatar
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 &...
Mokrane's user avatar
  • 159
0 votes
0 answers
60 views

Exponential of a special matrix

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}\...
matteogost's user avatar
0 votes
0 answers
13 views

Is there a way to increase the speed of multiplying $(-x^T\delta\ x )$

The x matrix has a size of 1024x1 and the $\delta$ has a size of 1024x1024. Delta is also a symmetric and sparse matrix. I am using the following equation to calculate a variable inside a loop. $$x^T\...
demirel123's user avatar
1 vote
0 answers
14 views

Sparse least squares where the coeefficient matrix is not stored explicitly

Consider a bounded linear operator $A : U \to V$ where $U$ is finite dimensional and where $V$ is a separable Hilbert space, or with large dimension such that $A$ cannot be stored explicitly, being ...
Jas Ter's user avatar
  • 1,539
1 vote
1 answer
135 views

How to understand each optimization step of Jacobi Iterative

Q: I saw Yousef Saad said "The Jacobi iteration determines the i-th component of the next approximation so as to annihilate the i-th component of the residual vector" in his book <<...
C Lei's user avatar
  • 171
1 vote
0 answers
499 views

Measure of closeness of a matrix to the block diagonal form

Is there a well-behaved measure for closeness of a matrix to the block diagonal form? Permutations of rows and columns are assumed to be allowed. This thread discusses the closeness to the diagonal ...
Sahand Rezaei's user avatar
2 votes
0 answers
162 views

Reordering vertices of a graph to make the adjacency matrix a block matrix with band-shaped blocks

Let $G = (V, E)$ be a sparse oriented graph with $n$ vertices (i.e. no loops, no multi-edges, about 1-5% of all possible $n\cdot(n-1)/2$ edges are present). The value of $n$ is about $100$. Let $A$ be ...
Dmitry D. Onishchenko's user avatar
1 vote
0 answers
121 views

Failure to invert sparse matrix

I have a large block arrowhead matrix which has significant sparsity in the following pattern: $\mathbf{M} = \left( \begin{array}{c|c} \mathbf{A} & \mathbf{B}^{\top}\\ \hline \mathbf{B} & \...
Audrey's user avatar
  • 95
7 votes
1 answer
360 views

Sparse PCA vs Orthogonal Matching Pursuit

Can't wrap my head around the difference between Sparse PCA and OMP. Both try to find a sparse linear combination. Of course, the optimization criteria is different. In Sparse PCA we have: \begin{...
Natan ZB's user avatar
2 votes
0 answers
170 views

Solve Ax = b (A and b both large and very sparse), but only for the values in some rows of x

I have a linear system $Ax=b$ where: $A$ is square, large ($m$ and $n$ on the order of $10^5$), asymmetric, very sparse (around $0.05\%$ non-zeros) $b$ is very sparse (also $0.05\% - 0.1\%$ non-zeros)...
Alex's user avatar
  • 121
1 vote
0 answers
56 views

Why large linear systems of saddle point type are indefiniteness and often poor spectral properties?

I'm reading the paper "Numerical solution of saddle point problems" by Michele Benzi. In the abstract, he states that these types of large linear systems of saddle point are challenging due ...
ergch24's user avatar
  • 21
1 vote
1 answer
272 views

LSQR method for solving a linear equation with positive value constraint for one column of the solution

I am solving an overdetermined sparse linear problem (Ax= B) using a C code. The code is using the LSQR method to find the solutions. There are 6 unknowns for every equation. One of the solutions is a ...
Esi's user avatar
  • 13
1 vote
1 answer
112 views

Find a sparse surrogate matrix that performs as good as the original one

Let $A\in \mathbb{R}^{m \times n}$ be a dense matrix and $x$ is a given vector in $\mathbb{R}^n$. How can one solve the following problem or its relaxation to find a sparse matrix that acts like $A$? $...
Saeed's user avatar
  • 175
1 vote
1 answer
73 views

Solving a sparse vector $x$ from system $Ax=b$ at the fastest possible way?

I'm going to solve this linear system: $$Ax=b$$ Where $x$ is sparse. To do that, Inned to minimize this. This is called lasso regression. $$\nabla J = ||Ax - b||_2 + \lambda ||x||_1$$ Where $\lambda &...
euraad's user avatar
  • 2,964
2 votes
1 answer
428 views

Relationship between matrices whose singular values are the same

Motivation: I have two different matrices in $\mathbb{R}^{1000 \times 2048}$. $A_1$ is coming from an sparse optimization process whose objective is creating as much as zeros in $A_1$. In this sense, ...
Saeed's user avatar
  • 175
0 votes
0 answers
33 views

Simultaneously sparsifying symmetrical real matrices

Suppose that we have $m\in N_+$ symmetrical real matrix $A_i,i=1,2...m,A_i\in R^{n\times n}$. Can we find an orthogonal matrix $T\in R^{n\times n}, TT'=T'T=I$ such that all of $B_i=T'A_iT$ are sparse ...
Zhong Zheng's user avatar
0 votes
0 answers
160 views

Show that Restricted Isometry property implies Restricted nullspace property

I need to show that if matrix A satisfies the RIP then it also satisfies the RNP. I need to prove that each of the lemmas holds and then show that RIP implies RNP using the lemmas. Lemma 1: Let the ...
snaz's user avatar
  • 11
6 votes
1 answer
1k views

What does LSQR stand for

One of the most popular and efficient iterative methods to solve large sparse systems of equations in the least squares sense is LSQR. It is related to CGLS (Conjugate Gradient Least Squares) in that ...
Jens Renders's user avatar
  • 4,344
1 vote
0 answers
82 views

Can the block-Lanczos algorithm possibly converge faster than the single-vector Lanczos?

We use the Lanczos algorithm for finding eigenvalues and eigenvectors of large sparse real matrices to model atomic nuclei. However, for heavier nuclei and their higher energy states, the matrix ...
Daniel Langr's user avatar
1 vote
2 answers
308 views

Iteratively solving (sparse) homogeneous linear systems

Solving (sparse) non-homogeneous linear systems can be done iteratively, by using the LSQR algorithm or similar. However, in the homogeneous case, we have $Ax =0$, where we typically want to find the ...
Nathaniel Bubis's user avatar