search

asc-community / AngouriMath

New open-source cross-platform symbolic algebra library for C# and F#. Can be used for both production and research purposes.
https://am.angouri.org
MIT License
784 stars 74 forks source link

Characteristic polynomial #381

Open WhiteBlackGoose opened 3 years ago

WhiteBlackGoose commented 3 years ago

The problem here is that we cannot compute it straightforward. For example, if you symbolically, even via Gaussian elimination, compute a determinant of a matrix 6x6, you will get almost 500'000'000-complex expression, which is hard to simplify into a polynomial.

So there should be a separate algorithm for computing it.

mednik commented 3 years ago

There is a variation of the straightforward approach: https://en.wikipedia.org/wiki/Faddeev%E2%80%93LeVerrier_algorithm

SymPy uses an improvement over this called https://en.wikipedia.org/wiki/Samuelson%E2%80%93Berkowitz_algorithm , it performs no division so may be used in symbolic situations over arbitrary rings, however it looks like it is even slower.

Now if your matrices are over something good like R, C or F_p, there are some other approaches, as far as I understand you have to google "Krylov method for characteristic polynomial".