Re: [sage-devel] LELA for matrices?
On Jun 2, 2013, at 9:20 AM, Dima Pasechnik wrote: On 2013-06-01, Volker Braun vbraun.n...@gmail.com wrote: [...] On a related note, sparse matrices in Sage suck (dictionary of keys). Sparse matrices in LELA only suck slightly less (list of lists). For fast computation one should implement compressed sparse row/column, I think. IMHO one needs to create a framework where one can choose a backend for sparse matrices, rather than aim for a complete from scratch implementation. I don't know what kind of interface do these package exhibit to access/modify/compute with a sparse matrix (eg. Linbox VS numerical-stuff) There is a presumably standard sparse-blas API : http://math.nist.gov/spblas/ E.g. there is a kind of standard, in numerics world, implementation of sparse matrices, which comes with a lot of extra goodies (including such important things like sparse Cholesky factorization, etc): http://www.cise.ufl.edu/research/sparse/SuiteSparse/ A part of it, complete with a Python interface, is already in Sage, in CVXOPT. And part of this is accessible already through SciPy (for floating-point matrices) : http://docs.scipy.org/doc/scipy/reference/sparse.linalg.html#module-scipy.sparse.linalg http://docs.scipy.org/doc/scipy/reference/sparse.linalg.html --- Charles -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] LELA for matrices?
On Sunday, June 2, 2013 10:01:01 AM UTC+2, Charles Bouillaguet wrote: http://docs.scipy.org/doc/scipy/reference/sparse.linalg.html yes, i just wanted to point to that. this is the list of implementations, i.e. CSC/CSR (compressed sparse columns or rows) is already there. http://docs.scipy.org/doc/scipy/reference/sparse.html#sparse-matrix-classes h -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] LELA for matrices?
On Sunday, June 2, 2013 9:01:01 AM UTC+1, Charles Bouillaguet wrote: There is a presumably standard sparse-blas API : http://math.nist.gov/spblas/ Yes, though it doesn't seem to mandate any matrix storage format. So apparently you can't let it run on a given chunk of memory but you need to trust its internal (implementation-dependent) storage. Does anybody have any opinion on the performance of sparse blas and the reference implementation? -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] LELA for matrices?
Le 02/06/2013 19:28, Volker Braun a écrit : On Sunday, June 2, 2013 9:01:01 AM UTC+1, Charles Bouillaguet wrote: There is a presumably standard sparse-blas API : http://math.nist.gov/spblas/ Yes, though it doesn't seem to mandate any matrix storage format. So apparently you can't let it run on a given chunk of memory but you need to trust its internal (implementation-dependent) storage. Does anybody have any opinion on the performance of sparse blas and the reference implementation? Sparse Matrices are a big problem for people like me working in the field of numerical solution of PDEs (elliptic and parabolic ones); and nowadays, there are some interesting researches. - Whatever the data structure you use (and CSR or CSR like structures are used by everybody), the main problem is that the algorithms show a poor numerical intensity; let me explain: linear solvers are generally iterative krylov type methods (- evaluate a polynomial of the matrix times a vector): the arithmetic intensity is the ratio: q=bytes transfered between ram and cache /number of floating points performed q is very low with sparse matrices and the performances are typically bounded by memory bandwidth to much less than 1 gigaflop. To improve this, the best is to modify the algorithms (a bit too long to explain here!) to try to make more operations by byte transfered: I think nobody knows a miraculous data structure, and so we keep the CSR. - Ok, this is the scientific computing perspective, where you want to solve say Poisson equation in 3d with 10^9 unknowns. But I am not sure it is what we want to do in Sage, at least nowadays; you can solve moderate size systems with sparse matrices (say a 2d Poisson equation -- there are 5 non zero terms by line-- with 10^6 unknowns using SuperLU which is a *direct* method (LU adapted to sparse matrices), which uses CSR structures, and it will work very well. - In that case, I recall that the main problem will be actually to *create* the CSR structure: you want to enter non zero coefficients (i,j)- a_ij in any order. The mechanism used by by scipy (and thus sage) is very very slow much too slow (may be it changed... this must be tested). - Making CSR structures for other sets of coefficients is not difficult (at least in C++), if the coefficients have the same sizeof. t.d. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out. attachment: tdumont.vcf
Re: [sage-devel] LELA for matrices?
On Sunday, June 2, 2013 7:58:05 PM UTC+1, tdumont wrote: - In that case, I recall that the main problem will be actually to *create* the CSR structure: you want to enter non zero coefficients (i,j)- a_ij in any order. The mechanism used by by scipy (and thus sage) is very very slow I don't think you can eat the cake and have it, too... Setting entries in CSR is to be avoided. Though I thought that you'd just switch (to dictionary-of-keys, say) to generate the matrix and then compress it in one step. Or maintain a lazy-write cache as dictionary of keys. Is that still not fast enough? -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] LELA for matrices?
I would like to have some discussion about the roadmap for matrices in Sage. It seems that linbox has essentially been forked by LELA (http://www.singular.uni-kl.de/lela). Since it optionally contains M4RI, one would think that it is a good fit for Sage, too. Has anybody given any thoughts to switching Sage from linbox to LELA? In particular, Burcin and Martin should have an opinion and it would be nice to hear from them ;-) On a related note, sparse matrices in Sage suck (dictionary of keys). Sparse matrices in LELA only suck slightly less (list of lists). For fast computation one should implement compressed sparse row/column, I think. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-devel] LELA for matrices?
Hi, as far as I know LELA does not support the same operations as LinBox, it's not a straight-forward fork but a re-implementation of a subset (that's my understanding, anyway). it has some advantages, i.e., that some bits nicely generic, i.e., it should be fairly easy to add new matrix types by adding stuff like matrix-matrix multiplication and e.g. PLE decomposition is handled generically. Also, the main developer of LELA Bradford has left academia. He usually responds fairly quickly to e-mail and is up for helping out, but as far as I know nobody is actively developing LELA at the moment (I might be terribly wrong here!) On Saturday 01 Jun 2013, Volker Braun wrote: I would like to have some discussion about the roadmap for matrices in Sage. It seems that linbox has essentially been forked by LELA (http://www.singular.uni-kl.de/lela). Since it optionally contains M4RI, one would think that it is a good fit for Sage, too. Has anybody given any thoughts to switching Sage from linbox to LELA? In particular, Burcin and Martin should have an opinion and it would be nice to hear from them ;-) On a related note, sparse matrices in Sage suck (dictionary of keys). Sparse matrices in LELA only suck slightly less (list of lists). For fast computation one should implement compressed sparse row/column, I think. Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=getsearch=0x6532AFB4 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de signature.asc Description: This is a digitally signed message part.
Re: [sage-devel] LELA for matrices?
My understanding is that only a very small subset of linbox is wired into Sage. In particular, all the iterative methods for the [rank/minpoly/charpoly/det] of sparse matrices are not accessible yet, but they are Linbox's strong point. Currently, sparse matrices are converted to dense ones, and very generic cython code is then used. Recent versions of linbox have some support for (read-only) compressed row matrices. --- Charles Bouillaguet http://www.lifl.fr/~bouillaguet/ On Jun 1, 2013, at 6:48 PM, Martin Albrecht wrote: Hi, as far as I know LELA does not support the same operations as LinBox, it's not a straight-forward fork but a re-implementation of a subset (that's my understanding, anyway). it has some advantages, i.e., that some bits nicely generic, i.e., it should be fairly easy to add new matrix types by adding stuff like matrix-matrix multiplication and e.g. PLE decomposition is handled generically. Also, the main developer of LELA Bradford has left academia. He usually responds fairly quickly to e-mail and is up for helping out, but as far as I know nobody is actively developing LELA at the moment (I might be terribly wrong here!) On Saturday 01 Jun 2013, Volker Braun wrote: I would like to have some discussion about the roadmap for matrices in Sage. It seems that linbox has essentially been forked by LELA (http://www.singular.uni-kl.de/lela). Since it optionally contains M4RI, one would think that it is a good fit for Sage, too. Has anybody given any thoughts to switching Sage from linbox to LELA? In particular, Burcin and Martin should have an opinion and it would be nice to hear from them ;-) On a related note, sparse matrices in Sage suck (dictionary of keys). Sparse matrices in LELA only suck slightly less (list of lists). For fast computation one should implement compressed sparse row/column, I think. Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=getsearch=0x6532AFB4 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
