On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials

DOI10.1137/0202007zbMath0262.65033OpenAlexW2055580199WikidataQ114074411 ScholiaQ114074411MaRDI QIDQ5678372

Michael S. Paterson, Larry J. Stockmeyer

Publication date: 1973

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ec62a5429e9dafcf537021f4e50ef552cef8d393

Mathematics Subject Classification ID

Numerical computation of solutions to single equations (65H05) Algorithms in computer science (68W99)

Related Items

Computing primary solutions of equations involving primary matrix functions, Lifting and recombination techniques for absolute factorization, Implicit purification for temperature-dependent density matrices, Fast operations on linearized polynomials and their applications in coding theory, Efficient and accurate algorithms for computing matrix trigonometric functions, On polynomials with symmetric Galois group which are easy to compute, Few Product Gates But Many Zeros, Homomorphic lower digits removal and improved FHE bootstrapping, Bootstrapping for approximate homomorphic encryption, On the computation of minimal polynomials, cyclic vectors, and Frobenius forms, Simplified lower bounds for polynomials with algebraic coefficients, Computing the Wave-Kernel Matrix Functions, Sine series approximation of the mod function for bootstrapping of approximate HE, A note on the complexity of approximative evaluation of polynomials, Efficient and accurate computation for the \(\varphi\)-functions arising from exponential integrators, New Hermite series expansion for computing the matrix hyperbolic cosine, Efficient mixed rational and polynomial approximation of matrix functions, Calculating a function of a matrix with a real spectrum, Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications, Optimality of the Paterson-Stockmeyer method for evaluating matrix polynomials and rational matrix functions, On polynomial functions Modulo \(p^e\) and faster bootstrapping for homomorphic encryption, Efficient evaluation of matrix polynomials, Oblivious message retrieval, Fast Taylor polynomial evaluation for the computation of the matrix cosine, Univariate polynomial factorization over finite fields with large extension degree, High-order lifting for polynomial Sylvester matrices, Massively parallel sparse matrix function calculations with NTPoly, Euler polynomials for the matrix exponential approximation, Lower bounds for polynomials with algebraic coefficients, On Bernoulli series approximation for the matrix cosine, Efficient orthogonal matrix polynomial based method for computing matrix exponential, Efficient homomorphic comparison methods with optimal complexity, Substitution algorithms for rational matrix equations, On the additive complexity of polynomials, Localization in Matrix Computations: Theory and Applications, Bootstrapping for BGV and BFV revisited, Computing isomorphisms and embeddings of finite fields, Fast methods for resumming matrix polynomials and Chebyshev matrix polynomials., Efficient computation of the matrix cosine, Fast computation of special resultants, Computing Enclosures for the Matrix Exponential, Time-space tradeoffs in algebraic complexity theory, Faster stochastic trace estimation with a Chebyshev product identity, Two algorithms for computing the matrix cosine function, Fast amortized multi-point evaluation, A new efficient and accurate spline algorithm for the matrix exponential computation, Computing the matrix sine and cosine simultaneously with a reduced number of products, Computation of matrix gamma function, An efficient and accurate algorithm for computing the matrix cosine based on new Hermite approximations, Polynomial evaluation over finite fields: new algorithms and complexity bounds, Boosting the computation of the matrix exponential, Computing matrix functions solving coupled differential models, A new method to obtain lower bounds for polynomial evaluation, The functions erf and erfc computed with arbitrary precision and explicit error bounds, CHIMERA: combining ring-LWE-based fully homomorphic encryption schemes, Modular composition via factorization, Complexity measures and hierarchies for the evaluation of integers and polynomials, Evaluation of polynomials with super-preconditioning, Fast multivariate multi-point evaluation revisited, Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials, Solving engineering models using hyperbolic matrix functions, Polynomial Evaluation and Side Channel Analysis, An \(\Omega((n/lg\,n)^{1/2})\) lower bound on the number of additions necessary to compute 0-1 polynomials over the ring of integer polynomials, Comparison of methods for evaluating functions of a matrix exponential, The scaling and modified squaring method for matrix functions related to the exponential, A Point Counting Algorithm Using Cohomology with Compact Support, On Bernoulli matrix polynomials and matrix exponential approximation, Accurate and efficient matrix exponential computation, Matrix Inverse Trigonometric and Inverse Hyperbolic Functions: Theory and Algorithms, Lower bounds for the complexity of polynomials, On the representation of rational functions of bounded complexity, On evaluating multivariate polynomials over finite fields, Short addition sequences for theta functions, Efficient Multiple-Precision Evaluation of Elementary Functions, An Arbitrary Precision Scaling and Squaring Algorithm for the Matrix Exponential, Computing the Lyapunov operator \(\varphi \)-functions, with an application to matrix-valued exponential integrators, On the backward and forward error of approximations of analytic functions and applications to the computation of matrix functions, New Scaling-Squaring Taylor Algorithms for Computing the Matrix Exponential, New Algorithms for Computing the Matrix Sine and Cosine Separately or Simultaneously, Factorization of the tenth Fermat number, The Scaling, Splitting, and Squaring Method for the Exponential of Perturbed Matrices, Accelerated tower arithmetic, Lower bounds in algebraic computational complexity, Arbitrary Precision Algorithms for Computing the Matrix Cosine and its Fréchet Derivative, Efficient algorithms for the matrix cosine and sine, On the algebraic complexity of rational iteration procedures