Dubious Ways to Compute the Zeros of a Polynomial | Hacker News Reader

Dubious Ways to Compute the Zeros of a Polynomial

blogs.mathworks.com

41 pointsvector_spaces14 comments

The author writes about a competing Fortran implementation for computing zeros: "But their software is in Fortran. I was a big Fortran fan for a long time. I used to be considered one of the Fortran gurus at MathWorks. I now don't even have access to a Fortran compiler. So I can't try their stuff myself."

This seems like a dubious claim - the AMVW code seems to provide a makefile that compiles using the free GNU Fortran compiler: https://github.com/eiscor/eiscor

Yeah, I regularly link to LAPACK today and sometimes use gfortran on Ubuntu to do this. The associated learning curve could be gentler, but this is definitely not a lost art.

That's the Cleve Moler that wrote MATLAB, was a major contributor to LINPACK etc, and founded MathWorks. "one of the Fortran gurus at MathWorks" indeed. It would not surprise me at all that in 2022 he doesn't know how to fire up a Fortran compiler on his current computer or even whether his current computer has one installed.

Recently read some nice articles on the companion matrix. One cool One: how to find the polynomial whose eigenvalues are the squares of those of some given polynomial p? Ans: get the companion matrix for p, square it, and then get the characteristic polynomial for the squared matrix.

Yah, in short, any matrix operation where you can track the effect off the operation on the eigenvalues of the matrix will give you the same effect of polynomial roots.

I used to work in algebraic combinatorics, which provides maps between important objects in algebra, combinatorics, and geometry, allowing us to apply theorems across the domains. You would often have dead obvious observations on one side which were very difficult to prove on another; eg 'This particular eigenvalue is a positive integer because it is also the dimension of a vector space."

>You would often have dead obvious observations on one side which were very difficult to prove on another; eg 'This particular eigenvalue is a positive integer because it is also the dimension of a vector space.

This is interesting, could you give some other examples?

The blog title is an advertisement for talk which does not appear to be published online, and also admittedly doesn't offer 19 dubious ways.

https://www.math.purdue.edu/~yipn/543/matrixExp19-I.pdf

That paper discusses ways of computing a matrix exponential, rather than ways of computing polynomial zeros.

Computing the matrix exponential is equivalent to finding the eigenvalues of a companion matrix, which in turn is equivalent to finding the roots of its characteristic polynomial. If you have nineteen ways of computing a matrix exponential, then you have nineteen ways to compute the roots of a polynomial, assuming that polynomial is the CP of the matrix you are exponentiating.

I've just looked up "companion matrix" to double-check what you're saying.

> Computing the matrix exponential is equivalent to finding the eigenvalues of a companion matrix

No it isn't. This is a prank, right?

Just to be clear (assuming you're not talking nonsense on purpose): You're saying that you take a monic polynomial p(x), form its companion matrix C, and then use the exponential function to find the eigenvalues of C. But the eigenvalues of exp(C) are just exp of the eigenvalues of C, which are exp of the roots of p(x). If you're suggesting power iteration (or improvements to that, like the QR algorithm) then what does matrix exponential have to do with that? I think you're confusing the process of raising a matrix to a power (written as M^n) with computing the exponential of a matrix (written as exp(M) or e^M) -- these are not the same operation.

One dubious way would use the argument principle [1] (which requires numerical integration) and bisection.

[1] - https://en.wikipedia.org/wiki/Argument_principle

I can’t remember the math. But when I was in high school I remember stumbling on this paper or something similar while working on a 3d engine. I programmed my graphing calculator to use it and basically “cheated” my way through a large bit of calculus with some variations on the code for each type of problem. This was 20-something years ago, so I don’t remember the details except that it didn’t work for every real problem, but most textbook ones and it used matrices.

I think it is pretty cool that the main example he discussed was his own. Given his contributions to the field some arrogance would be understandable, but instead Cleve Moler appears to have remained a pretty down-to-earth dude.

Reply on news.ycombinator.com