Sparse matrices
 

I was looking for a formal definition to "sparse matrices" but I only found definitions too general. Ok, I know that a sparse matrix has a bunch of null terms and just a few non zero terms scattered, but, how many zero terms? Is there a relationship to define it?

Regards

rne

Re: Sparse matrices
 

You are trying to look at shades of gray and call them black or white. The best definition would be a functional one. At what level of sparcity and size is it more economical to use sparse-matrix techniques?

Full-matrix techniques ignore the fact that elements of the matrix might be zero, and store a lot of zeros and do a lot of multiplication by zero and additions of zero. For large matricies this easily gets out of hand, both in computational time and memory storage.

Sparse matrix techniques recognize that many matrix elements are zero and skip storing them and multiplying them and adding them. Sparse matrix techniques may have additional overhead in storage and programming, but this overhead does not grow very fast with matrix size compared with full matrix techniques, and for very large matricies becomes a negligible part of the computation.

Re: Sparse matrices
 

It was just curiosity since all definition seems to vague for me. A large number of zeroes does not say anything (at least for me). Regarding the sparse techniques involved you're completely right and I agree with you.

As an expression widely used in scientific computing there should be a precise relationship to define a sparse matrix. Something as simple as (number of zeroes/number of non-zeroes) > ??? %, voila! You've just got a sparse matrix.

>> At what level of sparcity and size is it more economical to use sparse-matrix techniques?

I will never know it since I can't define sparsity. I could say that even for a matrix with 5% or 10% of zeroes the use of sparse matrix techniques would pay the costs (indirect addressing by less memory storage and more flops), who knows?

There must be some studies about it (comparisons of the costs associated with dense and sparse techniques)