From octave-sources-request at bevo dot che dot wisc dot edu  Mon Nov 23 20:31:30 1998
Subject: sparse matrix package for octave
From: Andy+Alison Adler <adler at mondenet dot com>
To: octave-sources at bevo dot che dot wisc dot edu
Date: Mon, 23 Nov 1998 21:35:42 -0500

After announcing I was working on it about 6 times:
I present version 0.10 of my sparse matrix package.

Here is some sample code (from the test scripts I 
provide with the package)

   CCt=       spfun(CC,'trans');
   CCtSS=     spfun(CCt,'mul',SS);
   ZZ=        spfun(CCtSS,'mul',CC);
   ZZs=       spfun(ZZ,'extract',2,n,2,n);
   QF=        full(spfun(QQ,'extract',2,n,1,p));
   VV=        spfun(ZZs,'solve',QF,2);

which is equivalent to the MATLAB code

   ZZ=        CC'*SS*CC;
   ZZs=       ZZ(2:n,2:n);
   QF=        full(QQ(2:n,:));
   VV=        ZZs\QF;

The conversion functions: sparse, full, etc are provided.

You can download the package from
http://www.mondenet.com/~adler/octave/spfun/

Here is the README from the package:
_______________________________________________
This is a sparse matrix toolkit for octave based
on the SuperLU package.

ID: $Id: README,v 1.4 1998/11/24 02:03:47 andy Exp andy $

AUTHOR:  Andy Adler <adler at mondenet dot com>

COPYRIGHT:
Copyright (C) 1998 Andy Adler

You may do what you like with this code as long as you
   leave this copyright in place.  If you modify the code
   then include a notice that it was modified.

WARRANY:

This code has no warranty whatsoever. If it breaks anything, then it's
your problem.  You are invited to email me a detailed bug report. I may
take notice.  I may even try to help.  But it's still your problem.

SUPERLU COPYRIGHT:

/*
 * -- SuperLU routine (version 1.1) --
 * Univ. of California Berkeley, Xerox Palo Alto Research Center,
 * and Lawrence Berkeley National Lab.
 * November 15, 1997
 *
 */
/*
  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.
*/ 

HISTORY:

Version 0.10:

There are four entry points:
   spfun.oct, sparse.oct, full.oct, splu.oct, spfind.oct

   sparse, full and find, convert to and from sparse
     storage format 

   spfun allows you to do several sparse functions that
     are specified by:
   x= spfun(a,"functon",b , extraparameters)

   where a and b are sparse of full matrices,
   and function is one of
     trans   -> a'
     el_mul  -> a.*b
     mul     -> a*b
     solve   -> a\b
     solvex  -> expert solver with interative improvement
                and extimation of the condition number

INSTALLATION INSTRUCTIONS:

All files are found at http://www.mondenet.com/~adler/octave/sparse

Here are your options in order increasing complexity:

1. Download the compiled Linux executables (build under RedHat 4.2)
   A. www.mondenet.com/~adler/octave/sparse/spfun-linuxexe.tar.gz
   B. tar xvfz spfun-linuxexe.tar.gz
   C. octave -qf sp_test.m

2. Download the source with the necessary files and patches to
   the SuperLU libraries.
   A. www.mondenet.com/~adler/octave/sparse/spfun-wSuperLU.tar.gz
   B. tar xvfz spfun-wSuperLU.tar.gz
   C. cd spfun
   D. make

3. Download the source, and SuperLU, and the patches
   A. www.mondenet.com/~adler/octave/sparse/spfun.tar.gz
   B. www.netlib.org/scalapack/prototype/superlu.tar.gz
   C. tar xvfz spfun.tar.gz
   D. cd spfun 
   E. tar xvfz ../superlu.tar.gz 
   F. patch <superlupatch.diff
   G. make
   
The makefiles depend on octave being installed in /usr/local
If it's not, you need to edit the makefile. (mkoctfile needs
a -c option to compile to *.o but not link to *.oct)

MISSING FEATURES (TODO FILE)
(This is more or less in the order of importance, and
 probability of accomplishment)

0.  Bug fixes
    memory leaks
    limitations on matrix size
    unneccesary data copying

1.  Sparse solution: there is no code for
    sparse \ sparse
    full \ sparse
    inverse( sparse )
    sparse == sparse
    sparse == full
    sparse(index1,index2) = submatrix

2.  Sparse functions need to be rewritten to overload
    the Octave operators (I'll probably need help with
    this one)

3.  More "sophisticated" matrix operations
    eigenvectors
    chol
    SVD
    etc.

KNOWN AND PREDICTED BUGS AND FEATURES:

1.  The code does way too much copying of data. I didn't try to
    optimize that as I intend to write a sparse matrix data type
    for octave, which means that the index vectors will be
    stored as integers and won't need to be converted back and
    forth from double.

2.  Right now only real (double) matrices are supported, SuperLU
    has support for complex, so I'll be adding that in at some point.

3.  It probably leaks memory. I'll try to test this more carefully
    after I stop adding features.

4.  It does not support empty matrices properly. It may even have
    some problems with completely sparse (all zero) matrices in
    some cases.

5.  The attempt here is to provide compatability to the main MATLAB
    sparse matrix entry points. The SuperLU provides slightly different
    fuctionality to MATLAB, and, therefore this toolkit provides
    different features.

    For example, the column permutation algorithm (and approach) is
    different.

    Additionally, I don't intend to provide replacements for the
    MATLAB sparse functions I consider frills. eg sprand.m, treeplot.m
    If you desperately want these features, you can 1) write them 
    yourself (and then submit them to me, please) 2) hope that
    enough people beg me to write the features.

6.  Returns from mallocs are not checked. As I understand it, most
    OSs (and definitely Linux, on which I developped this) always
    give you a valid pointer, allowing you to overcommit memory.
    I'm leaving it to Octave to handle the out of memory signals.
    Email me if you know the right way to do this.

7.  SuperLU routines bail out on errors. They don't even let
    octave save it's variables. Someone will have to explain to
    me how to modify the SuperLU ABORT() to do this right.

8.  SuperLU uses the int data type as indices. Since ints are normally
    4 bytes (at least on i386 machines), this is not a great problem.
    There are a probaly still a few places where an int is used to refer
    to i+j*m, which means that sparse operations on matrices where
    m*n > maxint/2 may be buggy. I've tried to fix this, but there
    are probably some left.  Email me if you find any.

9.  Sparse solve is a little faster than the MATLAB equivalent, except
    it seems not to choose the factoring as well. Using a perm_c spec of
    2 for symetric matrices will get speed improvements of ~ 2.
    Ideally, the appropriate factoring should be chosen based on the
    input matrix. The test code in fem_test takes about 4.8s/solve
    on MATLAB 4.0/win95 and 4.45s/solve on Octave/linux2.0.30 on a
    486DX100 with 32MB. (The relevance of this comparison is,
admittedly,
    not obvious)