Numerical Analysis
and Computational Mathematics
Polynomial Computations
The research in this field concerns the design
and analysis of algorithms for solving problems involving polynomial computations.
The interplay between structured matrices and polynomial computations plays
an important role in our analysis. The main problems investigated
are related to the solution of (systems of) polynomial equations, polynomial
arithmetic, gcd and lcm computations, Euclidean algorithm, polynomial and
power series factorizations, spectral factorizations, matrix polynomials
and matrix power series, interpolation problems, orthogonal polynomials
and rational functions.Efficiency of the algorithms in terms of their complexity
and stability is pursued.
Collaborations:
G. Del Corso, G. Manzini, V. Pan.
Papers:
-
D.A. Bini, L. Gemignani, On the Euclidean scheme for polynomials having
interlaced real zeros, Proceedings of 2-nd Annual ACM Symposium on Parallel
Algorithms and Architectures, Crete, 1990, 254-258.
-
D.A. Bini, V. Pan, Parallel polynomial computations by recursive processes,
Proc. ACM SIGSAM Intern. Symp. on Symbolic and Algebraic Comp.,
294, 1990.
-
D.A. Bini, L. Gemignani, V. Pan, Improved parallel computations with matrices
and polynomials, Proc. 18-th Intern. Symposium on Automata, Languages
and Programming, Lectures Notes in Computer Science, 510, 520-531,
Springer 1991.
-
D.A. Bini, Complexity of polynomial computations, in Complexity of Structured
Computational Problems, Applied Mathematics Monographs, Comitato
Nazionale per le Scienze Matematiche del CNR, Giardini, Pisa, 1991.
-
D.A. Bini, L. Gemignani, On the complexity of polynomial zeros, SIAM
J. Comput. 21, 781-799 (1992).
-
D. A. Bini, Divide and conquer techniques for the polynomial root-finding
problem,
Proc. World Congress of Nonlinear Analists, Tampa, Florida,
August 1992, Walter de Gruyter, Berlin 1996.
-
D.A. Bini, V. Pan, Improved parallel polynomial division, SIAM J. Comput.
22,3, 617--626, 1993.
-
D.A. Bini, L. Gemignani, Fast parallel computation of the polynomial remainder
sequence via Bezout and Hankel matrices, SIAM J. Comput., 24,1,
63-77, 1995 .
-
D.A. Bini, G. Fiorentino, A multiprecision implementation of a poly-algorithm
for univariate polynomial zeros, Proc. of The POSSO Workshop on Software,
Paris, 1995, J.C. Faugère, J. Marchand, R. Rioboo editors.
-
D.A. Bini, G. Fiorentino, Adaptive Multiprecision Algorithm for Univariate
Polynomial Zeros, Proc. of the First International MATHEMATICA Symposium,
Computational Mechanics Publications, Southampton 1995, pp. 53--60.
-
D.A. Bini, Numerical Computation of Polynomial Zeros by Means of Aberth's
Method,
Numerical Algorithms, 13, 1996 179-200.
-
D.A. Bini, V. Pan, Graeffe's, Chebyshev, and Cardinal's processes for splitting
a polynomial into factors, J. Complexity, 12, 492-511, 1996.
-
D.A. Bini, B. Meini, On the solution of a nonlinear
matrix equation arising in queueing problems. SIAM J. Matrix Anal.
Appl. 17:906--926, 1996.
-
D.A. Bini, V. Burchielli, MPSolve: 1.0: A Fortran
90 package for the numerical computation of polynomial roots, Dipartimento
di Matematica Universita' di Pisa, 1997.
-
D.A. Bini, L. Gemignani, Fast fraction-free triangularization of Bezoutians
with applications to sub-resultant chain computation. Linear Algebra
Appl. , 284 (1988) 19-39.
-
D.A. Bini, L. Gemignani, B. Meini, Factorization
of analytic functions by means of Koenig's theorem and Toeplitz computations,
Technical report, Dipartimento di Informatica, Universita' di Pisa, 1998.
-
D.A. Bini, G. Fiorentino, On the parallel evaluation of a sparse polynomial
at a point, report, 1998.
-
D.A. Bini, G. Fiorentino, MPSolve: Numerical
computation of polynomial roots v. 2.0,
FRISCO report 1998.
-
D.A. Bini, G. M. Del Corso, G. Manzini, L. Margara, Inversion of Circulant
Matrices over Z_m, 25th International Colloquium on Automata
Languages and Programming (ICALP '98), to appear in Mathematics
of Computations.
-
D.A. Bini, G. Fiorentino, On the Parallel Evaluation of a Sparse Polynomial
at a Point, Numerical Algorithms, 1999.
-
D.A. Bini, G. Fiorentino, Design, Analysis and Implementation of a Multiprecision
Polynomial Rootfinder, to appear in Numerical Algorithms.
-
L. Gemignani , Computing a Factor of a Polynomial by means of Multishift
LR Algorithms , SIAM J. Matrix Anal. Appl. 19 (1998) 161-181.
-
L. Gemignani , Polynomial Root Computation by means of the LR Algorithm,
BIT 37 (1997) 333-345.
-
L. Gemignani, Computing a Hurwitz Factorization of a Polynomial, manuscript,
(1999).
-
L. Gemignani , Computing the Inertia of Bezout and Hankel Matrices, CALCOLO
28 (1991) 267-274.
-
L. Gemignani , Computationally Efficient Applications of the Euclidean
Algorithm to Zero Location, Linear Algebra Appl. 249 (1996) 79-91.
-
L. Gemignani , A Fast Iterative Method for Determining the Stability of
a Polynomial, J. Comput. Appl. Math. 76 (1996) 1-11.
-
L. Gemignani, A Hybrid Approach to the Computation of the Inertia of a
Parametric Family of Bezoutians with Applications to some stability problems
for bivariate polynomials, TR-97/08, Computer Science Department, University
of Pisa, (1997). To appear in Linear Algebra Appl.
-
L. Gemignani , Manipulating Polynomial in Generalized Form , TR-96/14,
Computer Science Department, University of Pisa, (1996).
-
L. Gemignani , GCD of Polynomials and Bezout Matrices, Proc of the ACM
International Symposium on Symbolic and Algebraic Computations , Maui,
Hawaii, U.S.A..
-
L. Gemignani , Rational Interpolation via Orthogonal Polynomials , Computers
Math. Appl. 5 (1993) 27-34.
-
L. Gemignani , Chebyshev Rational Interpolation, Numerical Algorithms 15
(1997) 91-110.
-
L. Gemignani , Fast and Stable Computation of the Barycentric Representation
of Rational Interpolants, CALCOLO 33 (1996) 371-388.
Software: