Hello Oscar, I have Added my *GSOC 2025 proposal : Implementation of Division based LU and Fraction-Free LU decomposition algorithms in sympy's DomainMatrix* on the wiki page <https://github.com/sympy/sympy/wiki/GSOC-2025-Application-Temiloluwa-Yusuf-:-Implementation-of-Division-based-LU-and-Fraction%E2%80%90free-LU-(fflu)-algorithms-in-sympy-Domainmatrix> I will appreciate your feedback/review on my proposal, if there are things that needs to be added or removed.
Temiloluwa On Saturday, 22 March 2025 at 13:36:04 UTC+1 Temiloluwa wrote: > Hello Oscar, I have completed my GSoC 2025 proposal on *implementing > fraction-free and division based LU decomposition algorithms for > DomainMatrix*. Given your expertise and past feedback, I would really > appreciate it if you could review my proposal and share your feedback. > > If you have any suggestions for improvements, I would be happy to refine > the proposal further. Here is the link to my proposal. I have granted > your access to the document. > > > https://docs.google.com/document/d/1cOMl-zlFq9ocGBMD7zN0XHKKOAgLNvfrRDSG26X0IGw/edit?usp=sharing > > Looking forward to your feedback. > > Best regards, > Temiloluwa > > > On Fri, 7 Feb 2025 at 18:14, Oscar Benjamin <[email protected]> wrote: > >> Hi Temiloluwa, >> >> Yes, these kinds of things would be good to have in SymPy. More >> important than adding many different factorisations though is having >> good implementations of the most important ones. I would say that just >> implementing fraction-free and division-based LU algorithms fully >> would make a suitable GSOC project. I suspect that you currently >> underestimate how much is involved in that even though you have a PR >> that implements the algorithm already. The additional things that are >> needed to complete the LU implementation are things like: >> >> - Both sparse and dense implementations of LU and FFLU for >> DomainMatrix (consider if any very different sparse algorithms are >> worth implementing). >> - Make use of python-flint for FLINT's FFLU function when possible and >> ensure that the outputs are comparable to the SymPy implementation. >> - Numerically stable version of LU for floats. >> - Matrix methods that call into the DomainMatrix methods making them >> accessible to users and speeding up end user calculations. >> - Upper and lower triangular solves for LU and fraction-free LU. >> - Solving over/under determined systems. >> - Make use of LU to compute other things like matrix inverse, RREF, >> nullspace. >> - Lots of timings and benchmarks to compare performance of different >> approaches for different domains, shapes, densities etc. Decide when >> different algorithms should be used. >> - Make it so that solve and Matrix.solve and other functions use >> LU-based solve if it is better. >> >> See also this PR which I did not finish but was intended to make all >> linear equation solving code go through a single place so that it >> could be optimised for all cases: >> >> https://github.com/sympy/sympy/pull/26000 >> >> Putting all of that sort of stuff together is more useful than adding >> other less frequently used factorisations. A good implementation of LU >> is a foundation for many other things so it is worth spending some >> time to make it as good as possible. As you have seen other things >> like QRD can be almost trivial to implement if they can leverage the >> LU decomposition. >> >> In general not all matrix factorisations that can be defined >> abstractly are actually suitable for exact or symbolic arithmetic >> rather than floating point arithmetic and vice versa. For example I am >> not sure that I have seen any implementation of the polar >> decomposition for exact numbers. Unless SymPy could provide something >> that is more useful than SciPy's polar function I'm not sure it is >> worth adding. Note that a high precision implementation should be part >> of mpmath rather than SymPy. The only value implementing this in SymPy >> would be if it could be exact but I don't know how you would compute >> the polar decomposition exactly or whether that is something that only >> makes sense for very small matrices. >> >> On Fri, 31 Jan 2025 at 21:13, Temiloluwa <[email protected]> wrote: >> > >> > Hello SymPy Community, >> > >> > My name is Temiloluwa, and I would like to propose the addition of more >> matrix decomposition methods (Schur, Polar, and Hermite Decomposition) as >> my project idea for Google Summer of Code (GSoC) 2025. >> > >> > I have successfully gotten a PR in for a QR decomposition method for >> DomainMatrix and I am currently finalizing a PLDU decomposition and a >> fraction-free QR decomposition (QRD) pull request for DomainMatrix, aimed >> at improving the GramSchmidt process >> > >> > From my exploration of the SymPy codebase, I have observed that the few >> matrix decomposition methods that exist are LU, QR, Cholesky variants and >> some others to name a few. However, important methods like: >> > >> > Schur Decomposition (A=QTQH) >> > Polar Decomposition (A=UP) >> > Hermite Decomposition (A=LDLH) >> > >> > are yet to be implemented. >> > >> > Integrating these decompositions would enhance SymPy’s linear algebra >> capabilities, particularly in eigenvalue computation and numerical >> stability. I look forward to discussing this further and receiving feedback >> from the community. >> > >> > Best regards, >> > Temiloluwa >> > >> > -- >> > 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 visit >> https://groups.google.com/d/msgid/sympy/008ee22b-e3c3-40b0-8565-18e2f1aef17cn%40googlegroups.com >> . >> >> -- >> 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 visit >> https://groups.google.com/d/msgid/sympy/CAHVvXxTQX8t9LB-cT5RfOv-t1vDZx%2B9PQD55bTht-gQr33XN8w%40mail.gmail.com >> . >> > -- 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 visit https://groups.google.com/d/msgid/sympy/5187ec75-1ae8-4383-ac68-c54c0588c256n%40googlegroups.com.
