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
0answers
18 views

Numerical calculation of eigenvalues of a sparse (companion) matrix

Given is the matrix $$H=\begin{pmatrix} 0&0&\dots&0&-p_0\\ 1&0&\dots&0&-p_1\\ 0&1&\dots&0&-p_2\\ \vdots&\vdots& \ddots &\vdots&\vdots\\ ...
3
votes
1answer
98 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 ...
0
votes
0answers
17 views

Sparse matrices, sparse accumulator and multiplication

I'm trying to implement the algorithm for multiplying two sparse matrices from this paper: https://crd.lbl.gov/assets/pubs_presos/spgemmicpp08.pdf (the first algorithm - 1D algorithm). What bothers me ...
1
vote
0answers
23 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 ...
0
votes
0answers
7 views

How to use spmv result to compute another spmv?

Suppose $A$ is $I \times I$ sparse matrix ($I \ge 50000$) and $q_i$ is $I \times 1$ size of column one-hot vector (only $k_i=1$ and other are $0$, $k_i$ is $i^{th}$ element of $q_i$). When I get $r_i =...
0
votes
0answers
15 views

sparse a dense matrix and preserving its singular values

I have a huge matrix, $G$, and I want to calculate all its singular values. I have a binary masking sparse matrix, $C$, which I use to make $G$ sparse; $G' = G\circ C$. However, $G'$ won't have the ...
1
vote
0answers
11 views

Anomaly in sparse recovery when support is known.

I am interested in oracle performance in sparse recovery when support is known and am stuck in an anomaly. Consider a sparse recovery of n dimensional vector with p observations, y = Xh + n, where X ...
1
vote
2answers
75 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 ...
1
vote
1answer
60 views

Efficiently invert threediagonal symmetric matrix

I need to invert a threediagonal symmetric $1000\times10000$ matrix (or of similar dimensions). Specifically I need to solve the following equation: $$Ax=b$$ with $$A=\begin{pmatrix}v_1&-\frac{dt}{...
0
votes
0answers
15 views

Finding the largest few eigenvalues and eigenvectors of a sum of a diagonalizable matrix and a diagonal matrix of lower rank?

Suppose I have an $n\times n$ matrix $X = AHA^{T}$ and a matrix $R$, which is a diagonal matrix of size $n^2 \times n^2$. The elements in $R$ lie on the diagonal and have a single value and there are $...
0
votes
1answer
22 views

In order to induce group sparsity, can we use $\left \| A \right \|_{1,1}$ instead of $\left \| A \right \|_{1,2}$?

Let's define $\left \| A \right \|_{p,q}$ as follows: $$\left \| A \right \|_{p,q} = \sum_{i=1}^n \left \| \alpha^i \right \|_q^p$$. Where $\alpha^i$ is the i-th row of the matrix A. The above norm is ...
1
vote
0answers
40 views

Approximate upper bound on eigenvalues of $I-A$ where $A$ is a sparse matrix wherein each row sums to 1.0

Suppose $A$ is a large matrix with the following properties: $A$ is $n\times n$ $A$ is sparse (with each row having at most 8 non-zero coefficients, regardless of $n$) $A$'s diagonal has only zeros. ...
1
vote
1answer
104 views

Null-Space Projection with a Long Sparse Matrix

I want to solve the classical projection problem: given $x_0:n\times 1$ and a sparse matrix $C: m \times n$, solve for: $$ x = \operatorname{argmin}|x-x_0|^2,\ s.t. \\ Cx = 0 $$ The three usual ways ...
0
votes
0answers
42 views

Eigenvectors of block diagonal matrix

Consider a finite dimensional block diagonal matrix $A$ over $\mathbb{C}$ given by $$ A = \bigoplus_i A_i, $$ where $A_i$ are mostly the 0 matrix (of some finite dimension), i.e. the matrix is very ...
2
votes
1answer
21 views

Iterative solver for linear least squares, involving a large sparse/structured r.h.s.

Let $B$ be a $n$ by $n$ matrix, and $A$ a $n$ by $m$ matrix. I'm looking for the variable $X$, of size $m$ by $n$, that approximately solves $A X = B$; more precisely, the matrix $X$ that minimizes ...
0
votes
0answers
26 views

Efficient inverse of sparse arrowhead matrix

I want to efficiently (pseudo) invert a large, square matrix that is highly sparse. The matrix is structured in a block arrowhead shape, given as follows: \begin{equation} \mathbf{M} = \underset{(np+d)...
1
vote
0answers
15 views

Show that norm is reduced in each iteration for weighted additive orthogonal projection

I'm stuck in the following problem from Saad's Iterative Methods for Sparse Linear Systems: In an additive projection procedure, the $k+1$th residual vector is $$\vec{r}_{k+1} = \sum_{i=1}^p w_i (I-...
0
votes
1answer
22 views

Removing non-diagonal entries from a PSD matrix keeps the PSD property?

I was thinking about positive semidefinite (PSD) sparse matrices and I began to wonder whether the following is true: Let $A$ be a PSD matrix and let $\bar{A}$ be obtained from $A$ by replacing some ...
0
votes
0answers
14 views

Faster Diagonal and Circulant Matrix processing

Currently I have a matrix $\mathbf{H}$ in a large sparse linear system $\mathbf{H} \mathbf{x} = \mathbf{b}$. Now, I can decompose this matrix into $$ \mathbf{H} =\sum_{n=0}^k \mathbf{D}_n\cdot \mathbf{...
0
votes
0answers
7 views

Reverse Cuthill-McKee output matrix

Given a sparse diagonal matrix does Reverse Cuthill-McKee algorithm produce always a diagonal matrix?
0
votes
0answers
17 views

Shrunken covariance matrix in the Sparse inverse covariance selection

The original version of the L1 regularization method uses sample covariance matrix ${\mathbf{S}}$ as follows: \begin{equation} \hat{\mathbf{\Omega}}= argmin_{\mathbf{\Theta}\succ 0} \bigg(tr(\...
1
vote
0answers
14 views

Optimizing the solution of a sparse linear system with a particular structure

I am trying to solve computationally a sparse linear system of the form $Ax=B.$ A is a square matrix, for example of size $1600\times 1600$ (the exact size depends on the parameters of my program). B ...
0
votes
0answers
47 views

Proving that a matrix is sparse

I have the following identity: $$L=(I-A)^TD^{-1} (I-A),$$ where $I$ is the identity matrix, $A$ is a $n \times n$ lower triangular matrix with no more than $m \ll n$ non-zero elements in each row and $...
0
votes
0answers
38 views

How to update/recalculate the inverse of matrix after changed one element's value?

I have a large sparse matrix A and have gotten its inverse matrix inv(A) . Then I need to change an element value to get a new ...
5
votes
1answer
60 views

Why does MINRES converge in 3 iterations on matrices of specific form?

The MINRES algorithm for solving $Ax = b$ for symmetric $A$ can be described as follows: The $k$-th iterate of the algorithm is $$x_k = \arg\min_{K_k(A)} \lVert Ax-b \rVert_2$$ where $K_k(A)=\text{...
0
votes
1answer
35 views

Solve banded linear system with large bandwidth but sparse interior band structure

Assume the linear system $Ax = b$, where $A$ is a $N \times N$ banded matrix with lower and upper bandwidth $l$, and $N >> l >> 1$. $A$ has the following structure: All entries of $A$ are ...
1
vote
0answers
108 views

Inverse a sparse matrix

I have a sparse singular matrix W where I want to find its inverse Q. My current method is to use $W*Q = I$ for an optimization process of approximating the convergence of cost function norm($I-W*Q$). ...
1
vote
1answer
37 views

Fast algorithms for long sequences of sparse matrix products multiplying a vector?

Context: Having worked with developing algorithms involving huuge linear least squares systems involving sparse matrices, so far I have mostly constructed these huge sparse matrices explicitly and ...
0
votes
0answers
17 views

Condition value of sparse matrix

I have a sparse matrix really ill-conditionned. I wondered if the places where the non zero values have an impact on the condition value. My matrix is PSD and what I'd like to know is if the condition ...
0
votes
0answers
26 views

Expressing OneHotEncoding as a linear algebra operation

In ML applications dealing with categorical variables, it is often required to transform them into a OneHotEncoded representation. For example, given a vector of categorical features, $x=(1,3,4,2,3)^T$...
0
votes
0answers
12 views

What can be said about the LU decomposition of matrices with the same sparsity pattern?

Consider a set of invertible matrices $A_i$, each with an LU decomposition $$ A_i = L_iR_i $$ or with partial pivoting $$ P_iA_i = L_iR_i $$ What can be said about the sets $L_i$, $R_i$, $P_i$? Is ...
0
votes
1answer
39 views

Vector density as a function of sparsity

Many works denote $\phi(x)$ as density of a vector. $$ \phi(x) = \frac{||x||_1^2}{d||x||_2^2} $$ where $x \in \mathbb{R}^d$. Can we say that this quantity decreases as we increase sparsity? For ...
1
vote
0answers
77 views

What is the complexity of determining the eigenvalues of a very sparse matrix?

Suppose I have an $n \times n$ matrix with $O(n)$ nonzero elements. With what time complexity could the eigenvalues or characteristic polynomial of this matrix be computed? More easily, suppose I ...
1
vote
1answer
105 views

Can the Thomas algorithm be used to solve banded matrices of any arbitrary size? (ie larger than tridiagonal, penta/septa/+diagonal systems)

I am working a product concerning the Poisson Equation. In this project, I end up with a very large square matrix. It's impossible to solve efficiently with simple Gaussian elimination, but the matrix ...
5
votes
2answers
270 views

General formula for $f(n)$

Let for $n\geq 3, C_n$ denote the $(2n) \times (2n)$ matrix such that all entries along the diagonal are $2$, all entries along the sub- and super-diagonal are $1$, all entries along the antidiagonal ...
1
vote
0answers
95 views

How to evaluate directly the determinant? [duplicate]

How does evaluate the determinant of the following $(2n+1)\times (2n+1)$ matrix? \begin{equation} \det A = \begin{array}{|cccccccccc|cc} 1 & -1 & 0 & \dots & 0 & ...
2
votes
2answers
118 views

How to determine direct solution of determinant?

How to show that the determinant of the following $(2n+1)×(2n+1)$ matrix $A$? \begin{equation} \det A = \begin{array}{|cccccccccc|cc} 1 & -1 & 0 & \dots & 0 & 0 &...
0
votes
0answers
24 views

How to “fill in” a 2d grid based on neighbors

I've got an array of elevations on a plane, but there are missing values. Specifically it is elevations I derived from lunar satellite data regarding the south pole. I'd like to use the data to make ...
0
votes
1answer
83 views

The inverse of a sparse triangular matrix

I am solving a sparse system of linear equations $Ax=b$, where $A$ is symmetric positive definite. My matrix is 3210 x 3210, with about 10 non-zero values per row. For a specific $A$, I will need to ...
1
vote
1answer
46 views

Multiplication of columns of matrix appended with identity matrix

I have a matrix $A \in \mathbb{R}^{n\times n}$. Let $\{a_1,a_2,\ldots,a_n\}$ be its columns. I want to find the product of the matrices $A_1 \times A_2 \times\dots \times A_n$ where $A_i=[e_1 \quad ...
0
votes
0answers
33 views

Universal Approximation Theorems for Sparse Networks

It is well-known, as shown in Hornik's papers, that feed-forward neural networks are dense in the spaces of continuous functions (uniformly on compacts) and the spaces of $L^p$ functions (for suitable ...
0
votes
0answers
81 views

Eigenvalues of sparse matrix

I want to calculate the eigenvector corresponding to the $0$ eigenvalue of a large, sparse singular matrix. However, if I try eigs(A,1,'smallestabs'), MATLAB has an ...
1
vote
0answers
59 views

Eigenvector of large sparse stochastic matrix

I have a large sparse matrix corresponding to a system of master equations for a continuous-time Markov chain. It's approximately $500,000 \times 500,000$, with a density of around $10^{-6}$. Is ...
2
votes
2answers
368 views

Diagonalization of very large (but very simple) sparse matrix

I have a $10^5 \times 10^5$ matrix and I need its smallest eigenvalue (not the the smallest in absolute value, but actually the lowest) and the associated eigenvector (I know the eigenvalue to be non-...
2
votes
0answers
131 views

Need to solve a linear system with a sparse n x n matrix

I am developing an application in C# language — an electric simulator that uses the node-voltage method in the AC frequency domain. I need to solve large systems of linear equations (over $\mathbb C$)...
1
vote
0answers
28 views

How to generate random sparse unitary with given density?

For my research, I need to generate sparse (complex-values) unitary matrices at random from a uniform distribution. It is not a problem for me to generate the generic unitary matrices using, e.g., ...
0
votes
0answers
24 views

How to solve linear system with sparse large matrix?

I have the following system that I need to solve. The matrix is large $n \times n$, where $n = Nz* Nr \approx 150000$ or larger. The matrix always has the following form: Just 5 diagonals at $Nz, 1, 0,...
1
vote
0answers
42 views

How to recover sparse circulant matrix based on its partial eigenvalues?

Suppose we have a right circulant matrix ($n \times n$) $$ C= \begin{bmatrix} c_0 & c_{n-1} & c_{n-2} & \cdots & c_1\\ c_1 & c_0 & c_{n-1} & \cdots & c_2\\ ...
2
votes
1answer
53 views

Cholesky solve for semi-definite system

I am thinking about the following linear algebra problem: $$ Ax = b $$ where $A$ is an $n$ by $n$ positive semi-definite matrix, in particular, it is rank $n-1$ with null space span$\{e=(1,1,\ldots,1)^...
1
vote
1answer
235 views

compute $C = AB^{-1}A^T$ without inverting B

Is it possible to compute $C = AB^{-1}A^T$ without computing the inverse of $B$ explicitly? A is $n \times m$ matrix. B is $m \times m$ matrix ($m \gg n$). Thus $C$ is much smaller than $B$. In the ...