Polynomial Algebra By Values Papers
Polynomial Algebra By Values
Polynomial Algebra by Values refers to doing polynomial algebra
solely given the values of the polynomial---that is, working in the
Lagrange basis. Several popular codes do this already, in certain
circumstances (ode45 and ode15s in Matlab, for example, represent
the piecewise polynomial interpolants they use in this way). The
point of this research thread is to see how much we can do directly
in the Lagrange basis, and why this is a good idea.
- The very first paper (unpublished, not even submitted):
Generalized Companion Matrices for Polynomials
not expressed in Monomial Bases . I wrote this paper in about 2000,
and tried to get my masters student Gurjeet Litt interested in this; we
used it in the Mapstone Lecture workshop at SUNY Geneseo in 2001.
It was never finished, but a Maple implementation of the Lagrange basis
matrices made it in to Maple 7. This implementation was changed to
reflect the "improved" formulation I arrived at later, as discussed below.
- The first paper (on the ORCCA Tech Reports page): Polynomial Algebra By Values at the ORCCA Tech Report page.
- The next three, presented at EACA held June, 2004 in Santander, Spain,
and appearing in the Proceedings (edited by Laureano Gonzalez-Vega and Tomas
- Generalized Companion Matrices in the Lagrange Basis , pages 317--322.
- The Bezout Matrix in the Lagrange Basis
(by Azar Shakoori), pages 295--299.
- Dividing Polynomials when you only know
their values (by Amir Amiraslani), pages 5--10.
- Bernstein bases are optimal, but, sometimes,
Lagrange bases are better with Stephen Watt, published in the SYNASC 2004
proceedings (Timisoara), MITRON press, pages 141--153. Stephen's talk slides are Here .
- On a Generalized Companion Matrix Pencil
for Matrix Polynomials Expressed in the Lagrange Basis , in Proceedings
of the 1st SNC meeting, Xi'an, China, July 2005, D. Wang and L. Zhi, eds,
pages 1--18. This paper discusses the
geometry of the conditioning of the eigenvalues of the companion matrix
pencil, and proves two theorems about placement of interpolation nodes
and their relationship to the conditioning of the eigenvalues. An
explicit formula for the resolvent is given.
- The Nearest Polynomial
with a given zero, Revisited , with Nargol Rezvani. This paper
will appear in the Sigsam Bulletin (Communications in Computer Algebra)
September 2005, vol 134, no. 3, pp 71--76. Nargol's Masters' thesis
extends this work to weighted norms (and gives a dual norm for a weighted
$p$-norm) and also implements Karmarkar and Lakshman's algorithm in the
degree-1 case, for any basis handled by MatrixPolynomialObjectImplementation,
in Maple: this includes monomial, many orthogonal, the Bernstein (Bezier),
Newton, and Lagrange bases.
- (On the ORCCA Tech Reports Page) The Nearest Polynomial with
Lower Degree Robert M. Corless and Nargol Rezvani, submitted June 30, 2006
(actually this has been rejected and needs revision---the main thing is that
we did not make connection with the CAGD literature, or explain ourselves very well. I think that the results are right and useful, but more needs to be clarified. Soon, I hope.) In the meantime, here is an Extended Abstract accepted to SNC , London, 2007.
- (Accepted April 17, 2007, to
Mathematics in Computer Science)
Pseudospectra of Matrix Polynomials that are Expressed in Alternative Bases
, with Nargol Rezvani and Amir Amiraslani. (Current revised version)
This grew out of the
poster for MITACS/CAIMS June 2006.
Here are some images: a still colour pseudospectrum
of a six by six matrix polynomial of degree 7 (an essentially scalar
matrix polynomial, so we know its spectrum easily) defined by P(lambda)
= p( lambda*T^(-1) ) where T is tridiagonal, has 1/2 on the superdiagonal,
1/2 on the subdiagonal except for the T[2,1] entry which is 1, and zeros
on the main diagonal. The eigenvalues of T are the roots of the Chebyshev
polynomial of degree 6. The scalar polynomial p is just t^7 - 1.
The still image (zipped) is symcolour.zip and
the animation is an interesting mandala.
- (submitted) Rayleigh Quotient Iteration
for finding polynomial eigenvalues (with Amir Amiraslani and Dhavide Aruliah).
[Hint: Never use alphabetical order with either of these
two authors. Rare for Dhavide to get beat, though.]
- (accepted to Theoretical Computer Science) LU factoring of generalized companion
matrix pencils with the same authors.
- (accepted Nov 2007 to IMA J Numer Anal)
Linearization of Matrix Polynomials
Expressed in Polynomial Bases (original title: Interpolation of Matrix-valued
functions using polynomial bases)
with Amir Amiraslani and Peter Lancaster. This version
was revised according to a reviewer's suggestions, and the title changed.
- (on the ORCCA Tech Reports page)
Geometric Applications of the Bezout Matrix in the Bivariate Tensor-Product Lagrange basis
Dhavide Aruliah, Robert M. Corless, Laureano Gonzalez-Vega, and Azar Shakoori, accepted to SNC 2007 .
- Companion Matrix Pencils for Hermite
Interpolants , extended abstract accepted for SNC 2007 . This is joint work with Dhavide Aruliah, Robert M. Corless, Laureano Gonzalez-Vega, and Azar Shakoori.
- Files for my talk at the
Oxford Summer School on Solving Polynomial Equations.