Bibliography

AGR88

J. Ambrosiano, L. Greengard, V. Rokhlin, The Fast Multipole Method for Gridless Particle Simulation, Computer Physics Communications, 48, 115-125, 1988.

AHU74

A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1974 (first edition), 1976 (second edition).

BA80

R. R. Bitmead, B. D. O. Anderson, Asymptotically Fast Solution of Toeplitz and Related Systems of Linear Equations, Linear Algebra Appl., 34, 103-116, 1980.

BEPP97

H. Brönnimann, E. Z. Emiris, V. Y. Pan, S. Pion, Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision, Proc. 13th Ann. ACM Symp. on Computational Geometry, 174-182, ACM Press, New York, 1997.

BEPP99

H. Brönnimann, E. Z. Emiris, V. Y. Pan, S. Pion, Sign Determination in Residue Number Systems, Theoretical Computer Science, 210, 1, 173-197, 1999.

BGY80

R. P. Brent, F. G. Gustavson, D. Y. Y. Yun, Fast Solution of Toeplitz Systems of Equations and Computation of Padé Approximations, J. of Algorithms, 1, 259-295, 1980.

BMP98

D. Bondifalat, B. Mourrain, V. Y. Pan, Controlled Iterative Methods for Solving Polynomial Systems, Proc. Annual ACM-SIGSAM Intern. Symp. on Symb. and Algebr. Comp. (ISSAC'98), 252-259, ACM Press, New York, 1998.

BP94

D. Bini, V. Y. Pan, Polynomial and Matrix Computations, vol. 1: Fundamental Algorithms, Birkhäuser, Boston, Massachusetts, 1994.

BSS89

L. Blum, M. Shub, S. Smale, On a Theory of Computations Over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines, Bull. of Amer. Math. Soc., 21, 1-46, 1989.

Cad88

J. A. Cadzow, Signal Enhancement: A Composite Property Mapping Algorithm. IEEE Trans. on Acoust., Speech, Signal Processing, ASSP-36, 39-62, 1988.

CaW90

J. A. Cadzow, D. M. Wilkes. Signal Enhancement and the SVD, Proceedings of the 2nd International Workshop on SVD and Signal Processing, University of Rhode Island, Kingston, RI, 144-151, 1990.

CCC98

P. Chin, R. M. Corless, G. F. Corliss, Optimization Strategies for the Approximate Gcd Problem, Proc. Intern. Symp. on Symb. and Algebraic Comp. (ISSAC '98), 228-235, ACM Press, New York, 1998.

CGR87

J. Carier, L. Greengard, V. Rokhlin, A Fast Adaptive Multipole Algorithm for Particle Simulation, SIAM J. Sci. Stat. Comput., 9, 4, 669-686, 1988.

CGTW95

R. M. Corless, P. M. Gianni, B. M. Trager, S. M. Watt, The Singular Value Decomposition for Polynomial Systems, Proc. Intern. Symp. on Symbolic and Algebraic Comp. (ISSAC '95), 195-207, ACM Press, New York, 1995.

DeM94

B. De Moor, Total Least Squares for Affinely Structured Matrices and the Noisy Realization Problem, IEEE Trans. Signal Processing, 42, 3104-3113, 1994.

EGL96

I. Z. Emiris, A. Galligo, H. Lombardi, Numerical Univariate Polynomial GCD, AMS-SIAM Summer Seminar in Applied Math.: Mathematics of Numerical Analysis, Park City, Utah, 1995, (J. Renegar, M. Shub, S. Smale editors), Lectures in Applied Math., 32, 323-344, Amer. Math. Soc., Providence, R.I., 1996.

EGL97

I. Z. Emiris, A. Galligo, H. Lombardi, Certified Approximate Polynomial GCDs, J. of Pure and Applied Algebra, 117/118, 229-251, 1997.

EP97

I. Z. Emiris, V. Y. Pan, The Structure of Sparse Resultant Matrices, Proc. of Annual ACM-SIGSAM International Symp. on Symb. and Alg. Comp. (ISSAC'97), 189-196, ACM Press, New York, 1997.

Gat86

J. von zur Gathen, Parallel Arithmetic Computations: A Survey, Proc. Math. Foundation of Computer Science, Lecture Notes in Computer Science, 233, 93-112, Springer, Berlin, 1986.

Ger87

A. Gerasoulis, A Fast Algorithm for the Multiplication of Generalized Hilbert Matrices with Vectors, Math. of Comp., 50, 181, 179-188, 1987.

GO94

I. Gohberg, V. Olshevsky, Complexity of Multiplication with Vectors for Structured Matrices, Linear Algebra and Its Applications, 203, 163-192, 1994.

GKO95

I. Gohberg, T. Kailath, V. Olshevsky, Fast Gausian Elimination with Partial Pivoting for Matrices with Displacement Structure, Math. of Computation, 64, 1557-1576, 1995.

GR87

L. Greengard, V. Rokhlin, A Fast Algorithm for Particle Simulation, J. Comput. Physics, 73, 2, 325-348, 1987.

He74

P. Henrici, Applied and Computational Complex Analysis, 1, Wiley, New York, 1974.

Hei95

G. Heinig, Inversion of Generalized Cauchy Matrices and the Other Classes of Structured Matrices, Linear Algebra for Signal Processing, IMA Volume in Math. and Its Applications, 69, 95-114, Springer, 1994.

Hou77

D. G. Hough, Explaining and Ameliorating the Ill Condition of Zeros of Polynomials, Ph.D. Thesis, Computer Science Dept., Univ. of California, Berkeley, 1977.

HS96

V. Hribernig, H.J. Stetter, Detection and Validation of Clusters of Polynomial Zeros, J. Symb. Comp., 1996.

KKM79

T. Kailath, S.Y. Kung, M. Morf, Displacement Ranks of Matrices and Linear Equations, J. Math. Anal. Appl., 68, 2, 395-407, 1979.

KL96

N. Karmarkar, Y. N. Lakshman, Approximate Polynomial Greatest Common Divisor and Nearest Singular Polynomials, Proc. Ann. ACM-SIGSAM Intern. Symp. on Symb. and Algebraic Comp. (ISSAC'96), 35-39, 1996.

KM94

N. Karcanias, M. Mitrouli, A Matrix Pencil Based Numerical Method for the Computation of GCD of Polynomials, IEEE Trans. on Automatic Control, 39, 5, 977-981, 1994.

KR90

R. Karp, V. Ramachandran, A Survey of Parallel Algorithms for Shared Memory Machines, Handbook for Theoretical Computer Science (J. van Leeuwen editor), 869-941, North Holland, Amsterdam, 1990.

L81

D. Lazard, Resolution des Systems d'Equations Algebrique, Theoretical Computer Science, 15, 77-110, 1981.

Lei92

F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees & Hypercubes, Morgan Kaufmann Publishers, San Mateo, California, 1992.

M80

M. Morf, Doubling Algorithms for Toeplitz and Related Equations, Proc. IEEE Internat. Conf. on ASSP, 954-959, IEEE Computer Society Press, 1980.

MP98

B. Mourrain, V. Y. Pan, Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations, Proc. 30th Ann. ACM Symp. on Theory of Computing, 488-496, ACM Press, New York, 1998.

MP98a

B. Mourrain, V. Y. Pan, Multivariate Polynomials, Duality and Structured Matrices, Research Report No. 3513, INRIA, Sophia Antipolis, France, 1998, and MSRI preprint #1998-072, Mathematical Science Research Institute, Berkeley, California, 1998.

MP,a

B. Mourrain, V. Y. Pan, to appear.

NS91

M.-T. Noda, T. Sasaki, Approximate GCD and Its Application to Ill-Conditioned Algebraic Equations, J. Computational and Applied Mathematics, 38, 335-351, 1991.

OP98

V. Olshevsky, V. Y. Pan, A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problem and for Inversion and Factorization of Dense Structured Matrices, Proc. 39th Annual IEEE Symp. on Foundation of Computer Science, 192-201, IEEE Computer Society Press, 1998.

P89/90

V. Y. Pan, Computations with Dense Structured Matrices, Proc. ACM-SIGSAM Intern. Symp. on Symbolic and Alg. Comp. (ISSAC '89), 34-42, ACM Press, New York, 1989, and Math. of Comp., 55, 191, 179-190, 1990.

P92

V. Y. Pan, Complexity of Computations with Matrices and Polynomials, SIAM Review, 34, 9, 225-262, 1992.

P92a

V. Y. Pan, Parallel Solution of Toeplitz-like Linear Systems, J. of Complexity, 8, 1-21, 1992.

P93

V. Y. Pan, Concurrent Iterative Algorithm for Toeplitz-like Linear Systems, IEEE Trans. on Parallel and Distributive Systems, 4, 5, 592-600, 1993.

P95

V. Y. Pan, Optimal (up to Polylog Factors) Sequential and Parallel Algorithms for Approximating Complex Polynomial Zeros, Proc. 27th Ann. ACM Symposium on Theory of Computing, 741-750, ACM Press, New York, 1995.

P96

V. Y. Pan, Optimal and Nearly Optimal Algorithms for Approximating Polynomial Zeros, Computers and Mathematics (with Applications), 31, 12, 97-138, 1996.

P97

V. Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, 39, 2, 187-220, 1997.

P98

V. Y. Pan, Approximate Polynomial Gcds, Padé Approximation, Polynomial Zeros, and Bipartite Graphs, Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, 68-77, ACM Press, New York, and SIAM Publications, Philadelphia, 1998.

P98a

V. Y. Pan, Solving Polynomials with Computers, American Scientist, 86, 62-69, January-February 1998.

P,a

V. Y. Pan, Computation of Approximate Polynomial Gcds and an Extension, to appear in Information and Computation.

PBRZ,a

V. Y. Pan, S. Branham, R. Rosholt, A. Zheng, Newton's Iteration for Structured Matrices and Linear Systems of Equations, accepted for the SIAM volume: Fast Reliable Algorithms for Matrices with Structure (T. Kailath and A. Sayed editors), SIAM Publications, Philadelphia, to appear.

PCZ,a

V. Y. Pan, Z. Chen, A. Zheng, The Complexity of the Algebraic Eigenproblem, MSRI Preprint #1998-071, Mathematical Science Research Institute, Berkeley, California, 1998.

PLST93

V. Y. Pan, A. Sadikou, E. Landowne, O. Tiga, A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation, Computers & Math. (with Applications), 25, 9, 25-30, 1993.

PTCPS98

V. Y. Pan, M. A. Tabanjeh, Z. Chen, S. Providence, A. Sadikou, Transformations of Cauchy Matrices for Trummer's Problem and a Cauchy-like Linear Solver, Proc, 5th Ann. International Symp. on Solving Irregularly Structured Problems in Parallel (Irregular '98), Lecture Notes in Computer Science, 1457, 274-284, Springer, 1998.

PTCLS98

V. Y. Pan, M. A. Tabanjeh, Z. Chen, E. Landowne, A. Sadikou, New Transformations of Cauchy Matrices and Trummer's Problem, Computers & Mathematics (with Applications), 35, 12, 1-5, 1998.

PY99

V. Y. Pan, Y. Yu, Certified Numerical Computation of the Sign of a Matrix Determinant, Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM Press, New York, and SIAM Publications, Philadelphia, 1999.

PZ96

V. Y. Pan, A. Zheng, Fast Algorithms for Cauchy-like Matrix Computations and an Extension to Singular Toeplitz-like Computations, Preprint, 1996.

PZHD97

V. Y. Pan, A. Zheng, X. Huang, O. Dias, Newton's Iteration for Inversion of Cauchy-like and Other Structured Matrices, J. of Complexity, 13, 108-124, 1997.

PZHY97

V. Y. Pan, A. Zheng, X. Huang, Y. Yu, Fast Multipoint Polynomial Evaluation and Interpolation via Computations with Structured Matrices, Annals of Numerical Math., 4, 483-510, 1997.

Qui94

M. J. Quinn, Parallel Computing: Theory and Practice, McGraw-Hill, New York, 1994.

Ren89

J. Renegar, On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials, SIAM J. Comput., 18, 350-370, 1989.

Rok85

V. Rokhlin, Rapid Solution of Integral Equations of Classical Potential Theory, J. Comput. Physics, 60, 187-207, 1985.

Sc85

A. Schönhage, Quasi-GCD Computations, J. of Complexity, 1, 118-137, 1985.

SaSa97

T. Sasaki, M. Sasaki, Polynomial Remainder Sequence and Approximate GCD, ACM SIGSAM Bulletin, 31, 3, 4-10, ACM Press, New York, 1997.

vdV96

A. van der Veen, A Schur Method for Low-Rank Matrix Approximation. SIAM J. Matrix Anal. Appl., 17, 139-160, 1996.

War98

A. F. Ware, Fast Approximate Fourier Transform for Irregularly Spaced Data, SIAM Review, 40, 4, 838-856, 1998.