From octave-maintainers-request at bevo dot che dot wisc dot edu Thu Feb 12 11:34:09 1998 Subject: Sparse Matrices From: Andy Adler To: octave-maintainers at bevo dot che dot wisc dot edu Date: Thu, 12 Feb 1998 10:40:25 -0700 (MST) 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 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 adlera at njc dot org| | National Jewish Center,Denver,USA | 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