Opened 11 years ago

Last modified 7 years ago

#7723 needs_work enhancement

Sparse matrices for double fields

Reported by: dagss Owned by: jkantor
Priority: major Milestone: sage-6.4
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Dag Sverre Seljebotn Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Here's the beginnings of my work on sparse double matrices.

This is based on 4.3.rc0. Note that I have *not* run the entire Sage test suite, only tests in the matrix package. I'm happy to run the entire suite once I know the final revision this will be rebased to, but 4.3.rc0 produces a few test failures in itself (=noise I'm not bothering with for the moment).

There are three patches, which should be applied and reviewed in this order:

  • generic_multiply lets one override matrix multiplication with different parents. This is in a seperate patch because it changes structure/element.pxd, causing a big recompile.
  • double_sparse is the main new classes
  • coo_format changes the matrix constructor to accept "coo=..." (see docstring in patch)

More comments:

  • I will not introduce seperate classes for real and complex -- there will be other subclasses (Hermitian, strictly-diagonal etc.) and I don't want to double the size of the hierarchy. There are other (and better) ways to get efficient getitem/setitem without a speed penalty (such as introducing a seperate ItemAccessor? protocol/class -- though for sparse matrices an if-test won't matter either).
  • Once this is accepted (and I have a general feel for what I do right and wrong) I hope to continue with solvers etc. (as I scratch my itches).

Attachments (4)

trac_7723-coo_format.patch (25.9 KB) - added by dagss 11 years ago.
trac_7723-double_sparse.patch (41.9 KB) - added by dagss 11 years ago.
trac_7723-generic_multiply.patch (4.7 KB) - added by dagss 11 years ago.
trac_7723-fixround1.patch (13.7 KB) - added by dagss 11 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 11 years ago by dagss

  • Status changed from new to needs_review

comment:2 Changed 11 years ago by dagss

  • Component changed from numerical to linear algebra

Changed 11 years ago by dagss

Changed 11 years ago by dagss

Changed 11 years ago by dagss

comment:3 Changed 11 years ago by was

  • Status changed from needs_review to needs_work

REFEREE REPORT:

  • trac_7723-generic_multiply.patch:

Looks good, except there is a missing word "have" in this documentation:

3485	        The matrices should both the same base ring and either both 
3486	        should be dense or both sparse. 

This doesn't cause any doctest failures, and factoring this code out is a good idea.

  • trac_7723-double_sparse.patch

Looks good.

  • trac_7723-coo_format.patch

This causes a bunch of doctest failures:

wstein@sage:~/build/referee/sage-4.3.rc0$         sage -t  devel/sage/sage/matrix/matrix_integer_2x2.pyx # 5 doctests failed
sage -t  "devel/sage/sage/matrix/matrix_integer_2x2.pyx"    
**********************************************************************
File "/scratch/wstein/build/referee/sage-4.3.rc0/devel/sage/sage/matrix/matrix_integer_2x2.pyx", line 266:
    sage: m.__iter__()
Expected:
    <listiterator object at ...>
Got:
    <generator object row_iterator at 0x3ddab90>
**********************************************************************
File "/scratch/wstein/build/referee/sage-4.3.rc0/devel/sage/sage/matrix/matrix_integer_2x2.pyx", line 397:
    sage: m.__invert__unit()
Exception raised:
    Traceback (most recent call last):
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_19[4]>", line 1, in <module>
        m.__invert__unit()###line 397:
    sage: m.__invert__unit()
    AttributeError: 'sage.matrix.matrix_integer_dense.Matrix_integer_de' object has no attribute '__invert__unit'
**********************************************************************
File "/scratch/wstein/build/referee/sage-4.3.rc0/devel/sage/sage/matrix/matrix_integer_2x2.pyx", line 400:
    sage: type(m.__invert__unit())
Exception raised:
    Traceback (most recent call last):
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_19[5]>", line 1, in <module>
        type(m.__invert__unit())###line 400:
    sage: type(m.__invert__unit())
    AttributeError: 'sage.matrix.matrix_integer_dense.Matrix_integer_de' object has no attribute '__invert__unit'
**********************************************************************
File "/scratch/wstein/build/referee/sage-4.3.rc0/devel/sage/sage/matrix/matrix_integer_2x2.pyx", line 407:
    sage: m.__invert__unit() == m^-1
Exception raised:
    Traceback (most recent call last):
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_19[8]>", line 1, in <module>
        m.__invert__unit() == m**-Integer(1)###line 407:
    sage: m.__invert__unit() == m^-1
    AttributeError: 'sage.matrix.matrix_integer_dense.Matrix_integer_de' object has no attribute '__invert__unit'
**********************************************************************
File "/scratch/wstein/build/referee/sage-4.3.rc0/devel/sage/sage/matrix/matrix_integer_2x2.pyx", line 409:
    sage: M([2,0,0,2]).__invert__unit()
Expected:
    Traceback (most recent call last):
    ...
    ZeroDivisionError: Not a unit!
Got:
    Traceback (most recent call last):
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/scratch/wstein/build/referee/sage-4.3.rc0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_19[9]>", line 1, in <module>
        M([Integer(2),Integer(0),Integer(0),Integer(2)]).__invert__unit()###line 409:
    sage: M([2,0,0,2]).__invert__unit()
    AttributeError: 'sage.matrix.matrix_integer_dense.Matrix_integer_de' object has no attribute '__invert__unit'
**********************************************************************
2 items had failures:
   1 of   5 in __main__.example_13
   4 of  10 in __main__.example_19
***Test Failed*** 5 failures.
For whitespace errors, see the file /scratch/wstein/sage//tmp/.doctest_matrix_integer_2x2.py
         [1.5 s]
exit code: 1024
 
----------------------------------------------------------------------
The following tests failed:


        sage -t  "devel/sage/sage/matrix/matrix_integer_2x2.pyx"
Total time for all tests: 1.5 seconds

I noticed a *massive* performance regression as a result of your patches:

OLD SAGE:
sage: s = random_matrix(RDF,100)
sage: time t =s*s
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.15 s


WITH YOUR PATCHES:
sage: s = random_matrix(RDF,100)
sage: time t =s*s
CPU times: user 0.91 s, sys: 0.00 s, total: 0.91 s
Wall time: 0.91 s

Ouch. These are both dense matrices. There must be something that got seriously messed up with re-factoring?

  • Why is there a backslash here in matrix_double_sparse.pyx:
            either as a single list of length ``nrows\*ncols``, or as a 
    

---

Overall I'm very happy and excited about this patch!! I'm really, really glad you're working on this, and would like to do anything I can to encourage this. It is critically valuable to the Sage project to get much better numerical sparse matrix support.

comment:4 follow-up: Changed 11 years ago by dagss

  • Status changed from needs_work to needs_review

The attached patch should address the above issues (I guess this should have been folded into the original patches? But I hope this is OK, I still have some way to go before getting to terms with using Mercurial/MQ in a patch-review process.)

Changed 11 years ago by dagss

comment:5 in reply to: ↑ 4 Changed 11 years ago by was

Replying to dagss:

The attached patch should address the above issues (I guess this should have been folded into the original patches? But I hope this is OK, I still have some way to go before getting to terms with using Mercurial/MQ in a patch-review process.)

I'm really glad you *didn't* fold this into the original patch, since it makes it much easier for me to see what you changed.

comment:6 Changed 11 years ago by was

  • Status changed from needs_review to positive_review

Looks great!

comment:7 Changed 11 years ago by dagss

  • Milestone changed from sage-feature to sage-4.3.1

comment:8 Changed 11 years ago by mhansen

I get failures applying trac_7723-coo_format.patch

comment:9 Changed 11 years ago by dagss

I can't reproduce this, applying on 4.3.1.alpha0.

Did you apply them in the wrong order? Apparently I messed up the order when uploading, sorry. The patches must be applied in this order:

trac_7723-generic_multiply.patch
trac_7723-double_sparse.patch
trac_7723-coo_format.patch
trac_7723-fixround1.patch

comment:10 Changed 11 years ago by mhansen

Ahh, thanks. I was doing it in the wrong order.

comment:11 Changed 11 years ago by rlm

  • Status changed from positive_review to needs_work
The following tests failed:

        sage -t -long devel/sage-main/sage/matrix/constructor.py # 1 doctests failed
        sage -t -long devel/sage-main/sage/categories/action.pyx # Segfault

comment:12 Changed 11 years ago by dagss

Ouch.

I have not idea when I can get back to this at the moment. Basically what has happened is that I bit the bullet and implemented my own numerical matrix class hierarchy which is usable without Sage (but loosely modeled after it). That ended up giving me the results I needed much faster...

The long-term goal is to perhaps try to merge this back into Sage, however as there's no real benefit for my own work in doing that I don't really know if or when.

(Anyone who finds this ticket because they need this functionality are welcome to send me an email and check the status.)

comment:13 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:14 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:15 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:16 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.