Sparse Matrices

[Andy Adler]

Hello,

I'm moving the discussion of Sparse Matrix support to here from
help-octave. After several people suggested different sparse matrix
libraries from which to build sparse matrix routines for octave,
I took a look at the SuperLU package
 <ftp.cs.berkeley.edu/pub/src/lapack/SuperLU>

The package is fairly large
-rw-rw-r--   1 andy     andy      1579843 Feb  2 16:57 superlu.tar.gz
but contains demos and other extras. The compressed source is
-rw-rw-r--   1 andy     andy       347648 Feb 12 08:58 superlu_src.zip

It's written in C++, and has code for sequential and multithreaded
calculation (I suspect multithreading would not be easy to implement in
octave). It contains code to
  Factor:  [L,U,p]= superlu(A)  unit lower triangular L, upper triangular U,    
                                and permutation vector p with A(p,:) = L*U. 
  Solve:   x = lusolve(A, b)    solution to the linear system A*x = b,         
  Estimate condition number:
  Equilibrate:
  Refine Solution:

The license is:
%  Copyright (c) 1994 by Xerox Corporation.  All rights reserved.               
%                                                                               
%  THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY                 
%  EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.                          
%                                                                               
%  Permission is hereby granted to use or copy this program for any             
%  purpose, provided the above notices are retained on all copies.              
%  Permission to modify the code and to distribute modified code is             
%  granted, provided the above notices are retained, and a notice that          
%  the code was modified is included with the above copyright notice.           

which should be compatible with the GPL octave.

The package includes *.mex files for linking to Matlab. I tried this on a
Sparc10 under Solaris and ran the test routines which showed that SuperLU
is 3.0 times faster than Matlab's sparse routines for large matrices
(4720x4720, nnz(A)=32164).

QUESTION: Is this a good package to link to octave?
          Does anyone have oppinions/better ideas?

PROPOSAL: A first try link to octave.

Initially it's probably best to write *.m and *.oct files to do sparse
math.  If these work well, jwe can probably be convinced to add a
sparse matrix data format internally, as well as exending the operators
to deal with sparse matrices.

SPARSE MATRIX FORMAT: SuperLU uses the Harwell-Boeing or (compressed
column) format. This is different to the Matlab internal sparse format.
The H-B format should probably be used internally. 

Thus a sparse matrix S would be S.nrow  -> number of rows
                                S.ncol  -> number of cols
                                S.nnz   -> number of nonzero elements
                                S.nzval -> vector of nonzero elements
                                S.rowind-> vector index to rows
                                S.colptr-> vector pointer to rows

FUNCTIONS TO WRITE:

sparse -> *.m file based on Matlab's sparse
  S= sparse(i,j,s,m,n,nzmax) uses the rows of [i,j,s] to generate an
    m-by-n sparse matrix with space allocated for nzmax nonzeros.
  S= sparse(A) generates sparse matrix S from full matrix A

sp_add             -> corresponds to A+B
sp_subtract        -> corresponds to A-B
sp_dot_times       -> corresponds to A.*B
sp_multiply        -> corresponds to A*B
sp_dot_divide      -> corresponds to A./B
sp_divide          -> corresponds to A/B
full               -> like Matlab 

superlu            -> *.oct file from *.mex file with SuperLU
lusolve            -> *.oct file from *.mex file with SuperLU


_____________________________________________________________________
Andy Adler,    | Pulmonary Physiology Unit         | Lab 303-398-1626
address@hidden | National Jewish Center,Denver,USA | Fax 303-398-1607

Great Advances in Medicine: "Nitroglycerine to Facilitate Fetal Extraction
       During Cesearean Delivery" Obstetrics and Gynecology,91:119-24,1998