5 ms·

Dubious Ways to Compute the Zeros of a Polynomial

41 points by vector_spaces 4y ago

withinboredom 4y ago
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.
onos 4y ago
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.
- sdenton4 4y ago
  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."
  - voldacar 4y ago
    >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?
lupire 4y ago
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.
- bmc7505 4y ago
  https://www.math.purdue.edu/~yipn/543/matrixExp19-I.pdf https://www.math.purdue.edu/~yipn/543/matrixExp19-I.pdf
  - jwmerrill 4y ago
    That paper discusses ways of computing a matrix exponential, rather than ways of computing polynomial zeros.
    - bmc7505 4y ago
      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.
      - ogogmad 4y ago
        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.
rav 4y ago
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 https://github.com/eiscor/eiscor
- chrchang523 4y ago
  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.
- buescher 4y ago
  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.
ogogmad 4y ago
One dubious way would use the argument principle [1] (which requires numerical integration) and bisection. [1] - https://en.wikipedia.org/wiki/Argument_principle https://en.wikipedia.org/wiki/Argument_principle
bee_rider 4y ago
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.

41 points by vector_spaces 4y ago

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.

onos 4y ago

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.

sdenton4 4y ago
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."
- voldacar 4y ago
  >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?

lupire 4y ago

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.

bmc7505 4y ago
https://www.math.purdue.edu/~yipn/543/matrixExp19-I.pdf https://www.math.purdue.edu/~yipn/543/matrixExp19-I.pdf
- jwmerrill 4y ago
  That paper discusses ways of computing a matrix exponential, rather than ways of computing polynomial zeros.
  - bmc7505 4y ago
    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.
    - ogogmad 4y ago
      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.

rav 4y ago

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 https://github.com/eiscor/eiscor

chrchang523 4y ago
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.
buescher 4y ago
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.

ogogmad 4y ago

One dubious way would use the argument principle [1] (which requires numerical integration) and bisection. [1] - https://en.wikipedia.org/wiki/Argument_principle https://en.wikipedia.org/wiki/Argument_principle

bee_rider 4y ago

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.