On Tue, Mar 29, 2011 at 7:52 AM, Tim Lahey <[email protected]> wrote: > On 03-29-2011, at 12:39 AM, Frank K. wrote: > >> I did some more research and it looks like there are algorithms that >> can be applied to sparse matrices that are more efficient than the >> ones used for dense matrices. I'll look into those algorithms more >> tomorrow and start putting together a proposal. I think that writing >> those alternate algorithms in addition to sparse matrix structures >> will make for an interesting proposal, anyway. >> >> I will start to put together my proposal tomorrow, and look for as >> much feedback as I can get! > > You need to be careful. Try to find sparse matrix algorithms for symbolic > matrices if possible. Not all sparse matrix algorithms work well for symbolic > matrices. The point of the algorithms is to eliminate non-zero entries, but > with sparse matrices, you can get new non-zero entries with naïve algorithms. > So, you'd increase the density. > > In my mind, just implementing sparse matrix storage is not a GSoC project. In > my sparse linear algebra course I took, we implemented one just as part of a > class assignment. So, you should be able to do sparse matrix storage in about > a week's work (at 40 hours/week) at the worst case. > > You'll definitely need dedicated sparse matrix algorithms, but hopefully, you > can hide the implementation behind the standard interface. So, a sparse > matrix and a dense vector multiplication will use a dedicated algorithm to > handle that case. > > Cheers, > > Tim. > > --- > Tim Lahey > PhD Candidate, Systems Design Engineering > University of Waterloo > http://about.me/tjlahey > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > >
There are some major confusions on this list about the difference between algorithms and storage. Yes, it is typical to use iterative algorithms with sparse matrices and factorizations with dense, but this is because sparse matrices are typically very large (1M -- 10^12 entries with 1000 -- 2B non-zeros). One will switch to things that don't fill in the matrix but SymPy will probably never be at this level. One can implement some Krylov subspace iteration algorithms, but its somewhat pointless (how do you evaluate a residual in symbols). Another algorithm ILU versus LU is also silly (basically it throws away small fill in entries but we have no way of saying what is small in symbolics). For this reason I suggest just implementing standard factorizations and dealing with the fill in as it happens if we get to the point that we need to do UMFPACK style direct factorizations we can do that the next summer. We practitioners only use "algorithms suited for sparse matrices" because of the size of the matrices which will not be an issue in SymPy. It would be good if you listed what algorithms are "better" for sparse matrices and we go from there. It is a weak project to just do the storage by itself, and unless there are many people who will use sparse matrices, it's not particularly relevant. For example I just use scipy or petsc4py for sparse things in python. With that said, some day SymPy will be much faster than it is today (or at least I hope) and such structures may be commonplace if they are there. The project becomes much more interesting if you take Ronan's point of view of redesigning the Matrix class or perhaps implementing more matrix factorizations (LU, QR, Cholesky, diagonalization, eigenvalues: L\Lambda R should be achievable over the summer). -- Andy -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
