Wednesday, October 6, 2010

The status of cl-sparsematrix

In 2008, I had to solve some linear equations of the form Ax=b, where A was a sparse matrix (usually a design matrix for B-splines). I wrote up a library called cl-sparsematrix in one afternoon, and put it on the web.

This was not a sophisticated library. It did three very basic things: it helped construct a sparse matrix using a hash-table, had a function to pack that up in CSC format, and finally, a function to call UMFpack via CFFI to solve the equation mentioned above. This was it. It worked fine for what I wanted to use it, but it was not a sophisticated sparse matrix library.

I didn't have a need for sparse matrices ever since, and the library succumbed to bit rot: some other libraries it depended on moved on, quite substantially in some cases, and now it doesn't even load cleanly. But I still get a few e-mails every month asking about this library. So apparently there is a need in the CL community for a sparse matrix library. I have no time to clean it up at the moment, and you are probably better off writing your own. The library is no longer available online, because it doesn't work and I don't want to mislead people who are looking for a sparse matrix library.

When LLA is finalized, I will include sparse matrix functionality at some point. But LLA is undergoing (yet another) major reorganization now — I think I finally figured out how to interface native Lisp arrays to LAPACK in the implementations that support pinned arrays. So sparse matrices are not on the immediate horizon. Unless, of course, I need to solve sparse systems again, and hack up yet another quick-and-dirty solution.

6 comments:

  1. I know you've withdrawn this package, but is the latest source available somewhere? I've been helping convert some C++ code which calls through to UMFPACK to work with more recent versions of that library for another project, and would be happy to take a stab at making this run again, if the sources are still somewhere I can grab them...

    ReplyDelete
  2. Jim (and anyone else who needs the source): just send me an e-mail.

    ReplyDelete
  3. Hello, I needed sparse matrices too (but I do not need to use external libraries) here is how I did it:

    [sorry this thing does accept pre html tag]

    (defclass sparse-matrix (t)
    ((data :accessor data :initarg :data)
    (default-value :reader default-value
    :initarg :default-value
    :initform 0.0d0)
    (rows :reader rows :initarg :rows
    :type fixnum :initform 0)
    (columns :reader columns :initarg :columns
    :type fixnum :initform 0)))

    (defmethod initialize-instance :after ((m sparse-matrix)
    &key &allow-other-keys)
    (unless (slot-boundp m 'data)
    (setf (data m)
    (make-hash-table))))

    (defmethod ref ((a sparse-matrix) i j)
    (let ((n (+ (* (columns a) i) j)))
    (multiple-value-bind (val present-p)
    (gethash n (data a))
    (if present-p val (default-value a)))))

    (defmethod (setf ref) (value (a sparse-matrix) i j)
    (unless (eql value (default-value a))
    (let ((n (+ (* (columns a) i) j)))
    (setf (gethash n (data a)) value))))

    ReplyDelete
  4. Tamas -- don't feel bad about packing up LLA for now. Your cross-implementation research and experimentation with pinned arrays is incredibly valuable. I learned a lot from you and wish I had the time now to do Lisp work again. (I am writing sparse matrix codes, though!)

    @Thibault Sparse matrices aren't much good unless you can make them talk with other thoroughly tested, well-written libraries out there. You'll at least want a routine that can convert between your representation and a standard interchange format, such as CSR or CSC or coordinate.

    ReplyDelete
  5. @HilbertAstronaut: I am not packing up LLA, it is actively developed. Only cl-sparsematrix is dormant - for the moment.

    ReplyDelete
  6. Oops, yes, sorry about that Tamas, replace LLA with cl-sparsematrix in my comment :-)

    ReplyDelete