# Tagged Questions

Problems in which an operator or function can be represented with asymptotically less data than the naive representation. Not limited to sparse matrices.

9 views

### Linear solve using CHLOMOD in C

I am using the open-source CHLOMOD (as here http://faculty.cse.tamu.edu/davis/suitesparse.html) in order to solve a linear system Ax=b (performing A/b=x) in my domain decomposition code but I am ...
27 views

### Block-tridiagonal symmetric parallel solver (software recommendation)

What are the fastest numerical methods / (Fortran) packages to solve in parallel (MPI / OMP) a linear symmetric block - tridiagonal system (double complex) where the RHS is a block vector (complex)? ...
33 views

### Sparse matrix format and sparse-matrix sparse-matrix multiplication

Good morning, I'm having some performance problems with my code dealing with the multiplication of big sparse matrices (stiffness and aerodynamic influence coefficient matrices). Mainly I have to ...
112 views

### Solve for $C$ such that $C^{T}AC$ is banded of given width

Given a symmetric matrix $A$, the Lanczos algorithm outputs $C$ such that $C^{T}AC$ is tridiagonal. Is there a generalization of this such that $C^{T}AC$ is banded of specific width $w$? Note that $C$...
189 views

### Compute sparsity pattern of matrix product $A*A$

Suppose we have a sparse matrix $A$. Is there any faster way to compute just the sparsity pattern of $A^2=A*A$ (I do not actually need to know what exactly the nonzero value are) than to compute the ...
51 views

### Probability of reconstructing a word using c substrings from a random sample

Consider a voice recording split into it's phonemes as our sample $S=(s_1,...,s_k) \in \Omega = P^k$. The number of phonemes is $|P| = 40$. Then I have a word $w = (w_1,...,w_n) \in P^n$. I want to ...
54 views

### Sparse Matrix Matrix multiplication terminology (SpGEMM or SpMM?)

I have seen sparse matrix-matrix multiplication commonly referred to as SpGEMM, which means general/generalised sparse matrix-matrix multiplication. I've seen it once or twice (forgot where) as SpMM. ...
60 views

69 views

### Sparse Matrix Reordering

Matrix reorderings are important for many direct solvers. Sometimes the objective is to reduce the bandwith or the generated fill in by LU Decomposition. I am interested in a reordering which reduces ...
133 views

### Constructing sparsity pattern of the Jacobian of a FORTRAN subroutine

I need to calculate the Jacobian matrix of a subroutine F(U). Both F and U are of size N(=O($10^5$)). Using Tapenade, I differentiated the routine in tangent mode. I cannot calculate the full Jacobian ...
107 views

### Choosing preconditioner for unsymmetric pressure-velocity coupled system

I'm working with pressure-velocity coupled systems. It means that instead of solving 4 different linear systems in segregated approach (1 for pressure and 3 for Ux, Uy, Uz), we can solve only one ...
120 views

### How to convert MPIAIJ to SEQAIJ matrix in petsc/petsc4py?

I am curious, if there is a function to convert MPIAIJ (distributed matrices in AIJ format) to a SEQAIJ matrix that lie on a single processor. It is possible to do such an operation for PETSc vectors ...
44 views

### Fortran solver for the Sparse LSE problem

I was wondering if there is a Fortran library that contains a solver for the Sparse LSE(linear equality-constrained least squares) problem $$min_{x}\|Cx-d\|^2 \text{ subject to } Ax=b$$ where $A$ ...
102 views

### solve linear system of equation of a large sparse symetric positive definite matrix

I want to invert large matrices ($10^4 \times 10^4$ to $10^6 \times 10^6$) but sparse (less than $100$ non-zero entries per line) on clusters with $16$ to $48$ processors per node. I'm looking for an ...
210 views

### High computational time in using backslash for soving sparse matrix

I built a sparse matrix A at each step as follows: % 1 < DX < 120000 A = sparse(i,j,s,DX,DX,6*DX) b = (1, DX) The ...
53 views

### Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
104 views

### Sparse Linear Algebra vs Dense Linear Algebra

I am interested in a reference in the literature that discusses the performance of Dense Linear Algebra (blas routines) and dense linear algebra (sparse blas routines). I am interested in knowing for ...
103 views

### Sparse matrix vector product using PETSC

I am trying to do a simple parallel sparse matrix vector multiplications using PETSC. My sparse matrix is a simple tridiagonal laplacian matrix, which is distributed over multiple processors using ...
775 views

### How to use the basic Sparse matrix operations (multiplication, .etc) in PyCUDA

I try to use sparse matrix operations in GPU in Python and now try to use PyCUDA with theano. But I can't find how to do sparse matrix and vector multiplication. I only got an example showing how to ...
115 views

### Why does symrcm create larger band width?

When I run the following (in Matlab) on a sparse matrix $A$, I get larger band width. The symrcm (symmetric reverse Cuthill-McKee permutation) is not guarenteed to ...
275 views

### Solve Ax=B where B is a matrix in parallell

I try to solve the problem $Ax=B$ where $A$ is a large sparse $n\times n$ matrix, and $B$ is a dense $n\times m$ matrix (here $n=754850$ and $m=182$). The backslash operator yields correct solution (<...
104 views

### Sparse iterative out-of-core parallel solver

Is there an iterative sparse parallel solver with out of core capabilities? I need to solve a very large system of equations. I have implemented direct sparse parallel solvers in core and out of core ...
62 views

### Sparse linear system of certain type

Let $n_1,n_2 \in \mathbb{N}$ and $n=n_1n_2$ and $b\in \mathbb{R}^n$. I have a SPD-matrix $A=(a_{i,j})\in \mathbb{R}^{n \times n}$ with $a_{i,j}=0$ if $|i-j| \notin \{0,1,n_1\}$. Can we solve the ...
71 views

### Iterative algorithms for sparsity using a function for operator A in Ax=b

I am going to solve an linear iterative inverse problem. I have two functions in matlab which one of them play the forward and ...
220 views

### calculating eigenvector components of a given vector

I have some vector $V$ which can be decomposed into the eigenspace of the hermitian sparse operator $M$: $V = \sum_i v_i \hat{m}_i$ Is there a way to find the $\hat{m}_i$ (the eigenvector itself) ...
83 views

### What is the cost of factorization for one-dimensional sparse problems?

In Golub and Van Loan's book, Matrix Computations, page 606, it is stated that: With standard discretizations, 2-dimensional problems can be solved with $O(n^{3/2})$ work and $O(n \log{n})$ fill-...
289 views

### Phase retrieval via SDP (semidefinite program) of 2D test image (Matrix completion)

In SDP based phase retrieval we have intensity measurement (abs(FFT2(x))^2) of the form A(xo) = |ak,x|^2 =b^2, phase retrieval is then find x that obeys A(xo)=b The quadratic measurements can be ...
50 views

### Is there an upper bound for fill-ins for indefinite triangular factorization?

For $A=LU$, or $A=LDL^T$ factorization, bandwidth is preserved when there is no pivoting. This is true even for indefinite A, see question. However, when there is pivoting band structure is destroyed, ...
191 views

### Time complexity for sparse direct solver for SPD system with respect to number of equations, bandwidth, number of nonzeros?

I am looking for information on the time complexity for solving sparse system Ax=b with direct solver. This system results from a finite-element discretization of an elliptic problem. The matrix A ...
73 views

### Is the bandwidth of indefinite A equal to its factor L in LDL^T?

In George, Liu, and Ng's book Computer Solutions of Sparse Linear Systems, it has been shown that bandwidth of $A$ is equal to bandwidth of its factors in $LL^T$.(section 4.3) However, I guess this is ...
196 views

### how to pick a submatrix of a sparse matrix quickly(matlab)

I have a large sparse matrix A and i want to pick the submatrix of it to do block jacobi iterations. For the blocks, i have get a matrix Q that contains the index of nonzero entries in its Jth column ...
94 views

### Solvers for stiff initial value ODEs with sparse Jacobian

What ODE solvers are optimized for solving stiff systems with sparse Jacobian? Such systems appear, for instance, when a parabolic PDE is discretized in space using typical finite difference or finite ...
259 views

### Condition number from incomplete Cholesky factorization

I'm having difficulties patching together from what I read about obtaining the condition number of a real, symmetric, positive definite sparse matrix. In my code, I found that there is incomplete ...
244 views

### Parallel solver for sparse matrices on unstructured grids

I am trying to solve Euler equations on unstructured grids. Consequently, the problem reduces to solving Ax=b where A is a ...
178 views

### Fastest linear solver for sparse positive semidefinite, striclty diagonally dominant matrix

What is the state of the art for fastest linear solver for sparse, positive semi definite and strictly diagonally dominant matrix with N varies from ~700 to ~3000, and about a 1/16 of the matrix is ...
What algorithm is more practically suited in terms of performance for solving the $\mathbf{Lx=b}$ equation, where $\mathbf{L}$ is a generic Laplacian matrix (associated to a strongly connected graph, ...