Some Recent Algebraic/Numerical Algorithms

Victor Y. Pan
Mathematics and Computer Science Department
Lehman College, City University of New York
Bronx, NY 10468
Internet: VPAN@LCVAX.LEHMAN.CUNY.EDU

Full paper in compressed Postscript *.ps.gz

Abstract:

Combination of algebraic and numerical techniques for improving the computations in algebra and geometry is a popular research topic of growing interest. We survey some recent progress that we made in this area, in particular, regarding polynomial rootfinding, the solution of a polynomial system of equations, the computation of an approximate greatest common divisor of two polynomials as well as various computations with dense structured matrices and their further applications to polynomial and rational interpolation and multipoint polynomial evaluation. In some cases our algorithms reach nearly optimal time bounds and/or improve the previously known methods by order of magnitude, in other cases we yield other gains, such as improved numerical stability.

Key words: algebraic/numerical algorithms, polynomial rootfinding, solution of a polynomial system of equations, approximate gcd, dense structured matrices, Toeplitz matrices, Cauchy matrices, polynomial interpolation, rational interpolation, polynomial evaluation, Trummer's problem.

1991 Mathematics Subject Classification : 68Q40, 65Y20, 65D99.