Publication:4314299

Publication date: 21 November 1994

interpolation; computational complexity; textbook; symbolic computation; fast Fourier transform; polynomials; power series; analysis of algorithms; parallel computations; exercises; numerical computing; algebraic computation; dense structured matrices

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

65-02: Research exposition (monographs, survey articles) pertaining to numerical analysis

65D05: Numerical interpolation

65D20: Computation of special functions and constants, construction of tables

65T50: Numerical methods for discrete and fast Fourier transforms

65Y05: Parallel numerical computation

65Y20: Complexity and performance of numerical algorithms

65Fxx: Numerical linear algebra

Related Items

Matrix structure and loss-resilient encoding/decoding, Bernstein-Bézoutian matrices, Polynomial equation solving by lifting procedures for ramified fibers, Split algorithms for skewsymmetric Toeplitz matrices with arbitrary rank profile, Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate, Iterative inversion of structured matrices, Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. I: Transformations, Diagonal pivoting for partially reconstructible Cauchy-like matrices, with applications to Toeplitz-like linear equations and to boundary rational matrix interpolation problems, Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding, On the complexities of multipoint evaluation and interpolation, An application of matrix computations to classical second-order optimality conditions, Bezout matrices, subresultant polynomials and parameters, Computing curve intersection by means of simultaneous iterations, Bernstein-Bezoutian matrices and curve implicitization, Optimal Karatsuba-like formulae for certain bilinear forms in GF(2), Degeneration of structured integer matrices modulo an integer, Solving structured linear systems with large displacement rank, Fast computation of determinants of Bézout matrices and application to curve implicitization, A computational study of ruled surfaces, Deformation techniques for sparse systems, Matrix inversion cases with size-independent tensor rank estimates, Fast fraction-free triangularization of Bézoutians with applications to sub-resultant chain computation, A stabilized superfast solver for indefinite Hankel systems, A fast block Hankel solver based on an inversion formula for block Loewner matrices, Techniques for exploiting structure in matrix formulae of the sparse resultant, Multidimensional structured matrices and polynomial systems, New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set, Fast rectangular matrix multiplication and applications, Sign determination in residue number systems, A new efficient algorithm for computing Gröbner bases $(F_4)$, Finding the radical of matrix algebras using Fitting decompositions, Representations of Toeplitz-plus-Hankel martrices using trigonometric transformations with application to fast matrix-vector multiplication, Improved parallel solution of a triangular linear system, Computations with infinite Toeplitz matrices and polynomials, Fast direct solution methods for symmetric banded Toeplitz systems, based on the sine transform, Structured matrices and Newton's iteration: unified approach, Newton's iteration for inversion of Cauchy-like and other structured matrices, Displacement-structure approach to polynomial Vandermonde and related matrices, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Algebraic and numerical techniques for the computation of matrix determinants, New PCG based algorithms for the solution of Hermitian Toeplitz systems, Matrix displacement decompositions and applications to Toeplitz linear systems, Factorizations of Cauchy matrices, Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: Application to queueing problems, Parallel algorithms for certain matrix computations, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., Inverse power and Durand-Kerner iterations for univariate polynomial root-finding, Non-skip-free M/G/1-type Markov chains and Laurent matrix power series, Condition number bounds for problems with integer coefficients, Predicting zero coefficients in formal power series computations., Symbolic and numeric methods for exploiting structure in constructing resultant matrices, New transformations of Cauchy matrices and Trummer's problem, Various new expressions for subresultants and their applications, On solving univariate sparse polynomials in logarithmic time, Computing Moore-Penrose inverses of Toeplitz matrices by Newton's iteration, An efficient solution for Cauchy-like systems of linear equations, Newton-like iteration based on a cubic polynomial for structured matrices, A family of modified regularizing circulant preconditioners for two-levels Toeplitz systems, Matrices in elimination theory, Solving degenerate sparse polynomial systems faster, A fast Hankel solver based on an inversion formula for Loewner matrices, Load-balanced parallel banded-system solvers., Computation of approximate polynomial GCDs and an extension, Barnett's theorems about the greatest common divisor of several univariate polynomials through Bezout-like matrices, A superfast solver for Sylvester's resultant linear systems generated by a stable and an anti-stable polynomial, Fast computation of discrete invariants associated to a differential rational mapping, Split algorithms for Hermitian Toeplitz matrices with arbitrary rank profile, An algebraic approach to approximate evaluation of a polynomial on a set of real points, Parallel computation of a Krylov matrix for a sparse and structured input, Matrix decompositions using displacement rank and classes of commutative matrix algebras, A fast, preconditioned conjugate gradient Toeplitz and Toeplitz-like solvers, Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant, Algebras of higher dimension for displacement decompositions and computations with Toeplitz plus Hankel matrices, A new complexity bound for the least-squares problem, Optimal and nearly optimal algorithms for approximating polynomial zeros, Rational interpolation and recursive solution of Löwner-Vandermonde systems of equations, New techniques for the computation of linear recurrence coefficients, Multivariate polynomials, duality, and structured matrices, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., Lifting/descending processes for polynomial zeros., Superfast algorithms for Cauchy-like matrix computations and extensions, Lifting and recombination techniques for absolute factorization, Computations with quasiseparable polynomials and matrices, Schur aggregation for linear systems and determinants, A new Gröbner basis conversion method based on stabilization techniques, The amended DSeSC power method for polynomial root-finding, Polynomial evaluation and interpolation on special sets of points, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, Fast computation of special resultants, Symmetric subresultants and applications, A fast method to block-diagonalize a Hankel matrix, On the complexity of the resolvent representation of some prime differential ideals, Method for finding multiple roots of polynomials, Finite type projective modules, crossed linear maps and generalized inverses. (Modules projectifs de type fini, applications linéaires croisées et inverses généralisés), Computationally efficient applications of the Euclidean algorithm to zero location, Block diagonalization and LU-equivalence of Hankel matrices, Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions, Resolution of the finite Markov moment problem, Parallel computation of determinants of matrices with polynomial entries, Inversion of circulant matrices over $\mathbf{Z}_m$, More on Electrostatic Models for Zeros of Orthagonal Polynomials, Korovkin tests, approximation, and ergodic theory, Treating the Exceptional Cases of the MeatAxe, On solving composite power polynomial equations, A Gröbner free alternative for polynomial system solving, Polynomials arising in factoring generalized Vandermonde determinants: An algorithm for computing their coefficients, On the geometry of Graeffe iteration, Solving matrix polynomial equations arising in queueing problems, A fast iterative method for determining the stability of a polynomial, Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields, Fast computation of a rational point of a variety over a finite field, General polynomial roots and their multiplicities inO(N)memory andO(N²)Time^∗