I have implemented almost all useful linear algebra algorithms and decompositions using exact/symbolic computations (and in some cases fraction-free algorithms) (eg REF, RREF, SNF, INVERSE, PSEUDO-INVERSE, LU, QR, RANK factorisations/decompositions, ROWSPACE, COLUMNSPACE, NULLSPACE etc).

Deja Bradshaw 2022-10-22 Answered
Exact SVD algorithm of matrix with symbolic entries
I am making a library with symbolic computations which supports matrices. A matrix may have symbolic entries (eg be over the ring of polynomials of a variable x ie Q [ x ]).
I have implemented almost all useful linear algebra algorithms and decompositions using exact/symbolic computations (and in some cases fraction-free algorithms) (eg REF, RREF, SNF, INVERSE, PSEUDO-INVERSE, LU, QR, RANK factorisations/decompositions, ROWSPACE, COLUMNSPACE, NULLSPACE etc). The only needed algorithm which I cannot do with exact/symbolic computations is SVD/EVD. I only find numerical algorithms which solve the problem numericaly / approximately and employing "irrational" computations (eg square roots) which are not exact (note: I dont mind if an exact/symbolic algorithm employs square roots, since I can handle these symbolicaly if needed without actually computing square roots).Any exact/symbolic algorithm for SVD/EVD or any way to compute SVD using one of the decompositions I already have and which are exact?
You can still ask an expert for help

Want to know more about Polynomial arithmetic?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

wespee0
Answered 2022-10-23 Author has 15 answers
Step 1
To answer my own question, it seems the answer is:
no exact/symbolic algorithm exists (or is likely to exist) for SVD/EVD
Essentialy the problem is equivalent to the eigenvalue problem:
A x = λ x
This problem is equivalent to:
d e t ( A λ I ) = 0
which is a polynomial equation of nth degree in λ and according to Abel-Ruffini theorem there is no general exact/closed form solution involving elementary functions and operations (which is what I need in my case, but there is no general closed form solution even if more complex functions are allowed).
Step 2
Since every monic polynomial can be the characteristic polynomial of a matrix, this means that there is no exact/closed form solution to the eigenvalue problem and no exact/closed form solution to the SVD problem (which can be rephrased as eigenvalue problem) except numerical approximations which unfortunately cannot be used with symbolic entries
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more