# Tag Info

### Rule of thumb for sparse vs dense matrix storage

For what it is worth, for random sparse matrices of size 10,000 by 10,000 vs. dense matrices of the same size, on my Xeon workstation using MATLAB and Intel MKL as the BLAS, the sparse matrix-vector ...

### 20% performance penalty for a nice software design

It's a question on what you spend your time on. For most of us, we spend 3/4 of the time programming and 1/4 of the time waiting for results. (Your numbers may vary, but I think the number is not ...
Accepted

### Why does sparse linear algebra have a low arithmetic intensity?

BLAS1-operations, BLAS2-operations, and sparse-operations share the same curse of low arithmetic intensity, that they perform $O(1)$ flops for each memory read (contrast this to a BLAS3-operation like ...
Accepted

### Rule of thumb for sparse vs dense matrix storage

All matrix operations are memory bound (and not compute bound) on today's processors. So basically, you have to ask which format stores fewer bytes. This is easy to compute: For a full matrix, you ...
Accepted

### Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system

I believe comparing an iterative method (multigrid) to a direct/exact method (Thomas) in terms of exact operation count isn't really meaningful. IIRC, Thomas operation count is $8N$ for any ...
Accepted

### How to efficiently implement Dirichlet boundary conditions in global sparse finite element stiffnes matrices

In deal.II (http://www.dealii.org -- disclaimer: I'm one of the principal authors of that library), we do eliminate whole rows and columns, and it is not too expensive overall. The trick is to use the ...
Accepted

### Solving linear system of the form $ABx=b$

Defining the auxiliary variable $y=Bx$ yields the following algebraically equivalent expanded system, \underbrace{\begin{bmatrix} 0 & A \\ B & -I \end{bmatrix}}_{K} \underbrace{\begin{...

### Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system

The short answer is that the Thomas algorithm will be faster than any iterative scheme for almost all cases. The exception would perhaps be applying a single iteration of a very simple iterative ...
Accepted

### How can a CG solver solve a non positive definite sparse matrix

I highly recommend the following read: J.R. Shewchuk, "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain" In short, if the matrix is non-positive definite, there is no ...

### Which C++ linear algebra library is probably the fastest on solving huge sparse [square matrix] linear system?

Eigen 3 is a nice C++ template library some of whose routines are parallelized. c.f. Eigen documentation The parallelization is OMP only, so if you intend to parallelise using MPI (and OMP) it is ...
Accepted

### Is there an iterative solver for dense matrices with possible zero diagonal entries?

Iterative Krylov-subspace solvers generally only require matrix-vector products and don't care whether or where there are zeros in the matrix. In your case, unless you have other information about the ...
Accepted

### 20% performance penalty for a nice software design

Very few scientific software developers understand good principles of design, so I apologize if this answer is a bit long-winded. From a software engineering perspective, the goal of the scientific ...

### Solving Lx = b for big sparse Laplacian matrices

Daniel Shapero's answer is excellent, but I felt I should add the following: Properly preconditioned iterative methods will almost certainly win here, unless your systems have a very, very special ...
Accepted

### Compute all eigenvalues of a very big and very sparse adjacency matrix

You can use the shift-invert spectral transform  and compute the spectrum band by band. The technique is also explained in my article . Besides the implementation in , an implementation is ...
Accepted