This is beautiful. I may need to use it. I have a couple of observations.
(1) "The Frobenius decomposition itself is a one-time precomputation costing
O(n^3) via polynomial Smith reduction..."
This is quite correct, but I have my own reservations about the overall speed as dimension grows. I need to implement a likely faster method for FrobeniusDecomposition.
(2) There is some support in the Algebra context for fast coefficient-list-based polynomial arithmetic (adding, multiplying, and the like). Some is shown for example here.
Also some here on p. 10.
A variant, not using the Algebra functions, is here. It might be less reliable though since it uses Fourier and that may give issues if precision requirements are insufficiently gauged.
https://www.mathematica-journal.com/2009/01/12/on-some-applications-of-the-fast-discrete-fourier-transform/
Also one can use ListConvolve directly to multiply polynomials expressed as coefficient lists.
I am fairly certain there is a more complete reference, likely by Paul Abbott in one of his TMJ columns. But I cannot seem to locate it. In any case, if you need some more examples just let me know and I will see what I can locate.
