Re: What is a sparse matrix ?

[Paul Kienzle]

On Apr 27, 2004, at 7:00 PM, Henry F. Mollet wrote:

> What is a sparse matrix?

With octave-forge, you can say:

        sparse(i,j,v,m,n)

which will create an mxn matrix A with A(i_k,j_k) = v_k for all k.

Octave-forge has two implementations: extra/fake-sparse is a
pure m-file version based on full matrices, and main/sparse is
a proper version which does not store zero elements.

I'm ignoring details, like what happens when element p and q
have the same indices.

>  Is it a matrix with few elements (sparse?) and lots
> of zeros?

It is a data structure for storing matrices.  It is more efficient than
storing every element if the matrix has few non-zero elements,
but less efficient when there are many non-zero elements.  The
cross-over point (both in storage and time) is around 1/3 full.

> Can somebody please interpret the following description?

They say they are storing a vector (the v_k above), with the added
restriction that the indices i_k,j_k need to be ordered, either along
the rows or down the columns.   I imagine they store the i_k and j_k
vectors as well, or some variation thereof.

I don't know what the template parameters <T,F,A> refer to.  One of
them is going to be the numeric type (float, double, complex<float>,
complex<double>, etc.).  Another could be the ordering (column
major vs. row major).  I can't tell from the description what the third
might be.

> Is a
> Leslie matrix A (with matrix elements on the first row and first
> sub-diagonal only and A = F + T) a sparse matrix?

Yes.  You can store this with only 2n elements rather than forming
a full n^2 matrix, so it is an excellent candidate for sparse storage.

> Henry
>
> Description
> The templated class sparse_matrix<T, F, A> is the base container 
> adaptor for
> sparse matrices. For a (m x n )-dimensional sparse matrix and 0 <= i < 
> m ,0
> <= j < n the non-zero elements mi, j are mapped via (i x n + j) for row
> major orientation or via (i + j x m) for column major orientation to
> consecutive elements of the associative container, i.e. for elements 
> k=mi1,j
> 1and k + 1 = m i2,j 2of the container holds i1< i 2or (i 1= i 2and j1< 
> j
> 2)with row major orientation or j1< j 2or (j 1= j 2and i1< i 2)with 
> column
> major orientation.

Paul Kienzle
address@hidden



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------