On Sun, 28 Feb 2021 at 10:38, Kartik Sethi <[email protected]> wrote: > > I was wondering if completing the tasks listed on > https://github.com/sympy/sympy/issues/20987 could be a Gsoc proposal.
Some of the things in that list are fairly trivial like "make Matrix use DomainMatrix for charpoly". The DomainMatrix charpoly method is there already and is efficient so it's just a case of changing the charpoly method of matrix to call that. Other things on the list are a bit more complex like "implement the Bareiss algorithm": that's not a complicated algorithm but implementing it efficiently with pivoting for sparse matrices takes a bit of work. Then other things are much more difficult like "Make risch use DomainMatrix" and are clearly beyond the scope of a GSOC proposal right now (unless you already have significant knowledge of the algorithm and its implementation in sympy). So a GSOC proposal could focus on only some of the things from that list. The list itself is very incomplete so there are plenty of other things that would make both DomainMatrix faster and other ways to make Matrix faster by using DomainMatrix. If you can think of anything then please suggest on the issue so that we can add it to the list. The most useful thing that a GSOC project could do is really just to make the whole DomainMatrix class a bit more complete, usable and documented so that it's easier for users and future contributors to make use of it and also make improvements to it. There are always contributors wanting to add basic matrix algorithms like SVD etc regardless of GSOC. I would personally rank a GSOC project more highly if it looks like a more involved piece of work that needs someone to spend a bit of time getting to know a particular part of the codebase. > There's a lot to do in that list and I can even add some other functions like > QR decomposition, Hessenberg Decomposition, SVD, Polar Decomposition etc. to > that list. Since DomainMatrix works over a domain or a field some algorithms make less sense for it. For example an algorithm that involves computing lots of square roots means taking repeated field extensions which would probably not be efficient with DomainMatrix. I'm not sure how easy it is to implement any of those with DomainMatrix but certainly if the algorithm boils down to operations like charpoly, and nullspace (like computing the eigenvectors or Jordan form does) then we can just make those core operations more efficient using DomainMatrix. I would begin with the trivial things like for example charpoly takes 11 seconds to compute the characteristic polynomial of this small 5x5 matrix of complex numbers: In [1]: M = randMatrix(5) + randMatrix(5)*I In [2]: %time p1 = M.charpoly() CPU times: use 11.4 s, sys: 67.4 ms, total: 11.5 s Wall time: 11.6 s It only takes a few milliseconds to do the same with DomainMatrix: In [4]: from sympy.polys.matrices import DomainMatrix In [5]: %time dM = DomainMatrix.from_Matrix(M) CPU times: user 552 µs, sys: 1e+03 ns, total: 553 µs Wall time: 558 µs In [6]: %time p2 = dM.charpoly() CPU times: user 2.77 ms, sys: 26 µs, total: 2.79 ms Wall time: 2.83 ms In [7]: Poly(p2, p1.gens, domain=dM.domain) == p1 Out[7]: True Making Matrix.charpoly faster then is a pretty trivial pull request at this stage. That would then speed up all the other operations that use charpoly (eigenvals, Jordan form etc). If you time various operations like this with Matrix then you can see what is slow and whether or not DomainMatrix can be used to speed things up. Ideally though we just use it for a small number of operations that are the core to other algorithms. The thing to pay attention to is what kinds of entries you have in the matrix and what domain the resulting DomainMatrix uses. DomainMatrix is faster for a matrix of integers but where it really makes a difference is something like the above which is a matrix of Gaussian integers or matrices that involve algebraic quantities like sqrt(2) or matrices with symbols in so that the entries are e.g. polynomials in x and y. -- Oscar -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAHVvXxREHu-mW1LXDRyhAs0nK5N84-9-exxiaH%2B_z9YO4Leryw%40mail.gmail.com.
