Using sparse/full to solve Ax = b

Hello, I am trying to solve for the vector x in Ax = b, where A is a square symmetric matrix with many zeros and b is a vector. I realize instead of immediately doing x = A\b it would be faster to make A sparse but I'm confused on implementing this.

Should I do:

A_sparse = sparse(A); 
x = A_sparse\b;

or

A_sparse = sparse(A); 
x_sparse = A_sparse\b; 
x = full(x_sparse);

or

A_sparse = sparse(A); 
b_sparse = sparse(b); 
x_sparse = A_sparse\b_sparse; 
x = full(x_sparse);

Thanks

Answer 1

[Christine Tobler]

If A is sparse and b is dense, x = A\b returns a dense matrix x, so no need for the "full" command. It's also not necessary to make b sparse before passing it to A.

Whether the sparse matrix solver is faster than the dense solver depends on the particular structure of your matrix. For small matrices (size <100), you are unlikely to see much improvement. Also, a larger matrix with 10-20% nonzero entries is typically still too dense to see much improvement from using a sparse algorithm.

Answer 2

[Ameer Hamza]

Here is a speed comparison of the different methods

dim = 5000;
A = rand(dim);
A(A<0.8) = 0;  % approximately 80 percent elemets are zero
b = rand(dim, 1);

tic
x1 = A\b;
toc

Elapsed time is 0.970270 seconds.  <---- least time

A_sparse = sparse(A); 
tic
x2 = A_sparse\b;
toc

Elapsed time is 4.490995 seconds.

A_sparse = sparse(A); 
b_sparse = sparse(b);
tic
x_sparse = A_sparse\b_sparse; 
x3 = full(x_sparse); 
toc

Elapsed time is 4.593132 seconds.

It shows that the first case with A\b will produce a fast solution even for sparse matrices. Note that this doesn't include the time taken for the creation of sparse matrix from the full matrix A. Although sparse matrix will save storage, but may not be able to allow faster calculation

[Qinzhuo Liao]

If changing it to "approximately 99.9 percent elemets are zero"

The sparse one will become faster than the original. :)

[Christine Tobler]

Agreed, Qinzhuo Liao.

Also, with sparse matrices, it's important where the nonzero entries are. In most cases, a matrix that has very few nonzero elements will also have those elements following some pattern. When nonzeros are placed completely at random inside of a matrix, this is usually quite bad for performance of a sparse direct solver as is used in A\b.