3,176 research outputs found
GCD of polynomials and Bezout matrices
No full textA new algorithm is presented for computing
an integer polynomial similar to the GCD of
two polynomials and , . Our approach uses structured matrix
computations involving Bezout matrices rather than
Hankel matrices. In this way we reduce the computational costs
showing that the new algorithm requires arithmetical
operations or Boolean operations,
where
Efficient inversion of matrix ϕ-functions of low order
No full textThe paper is concerned with efficient numerical methods for solving a linear system & phi;(A)x = b, where & phi;(z) is a & phi;-function and A E RNxN. In particular in this work we are interested in the computation of & phi;(A)-1b for the case where & phi;(z) = & phi;1(z) = ez -1 z ez - 1 - z & phi;(z) = & phi;2(z) = z2 . Under suitable conditions on the spectrum of A we design fast algorithms for computing both & phi;⠃(A)-1 and & phi;⠃(A)-1b based on Newton's iteration and Krylov-type methods, respectively. Adaptations of these schemes for structured matrices are considered. In particular the cases of banded and more generally quasiseparable matrices are investigated. Numerical results are presented to show the effectiveness of our proposed algorithm
A Fast Iterative Method for Determining the Stability of a Polynomial
No full textWe present an iterative numerical method for
solving two classical stability problems for
a polynomial of degree : the
Routh-Hurwitz and the Schur-Cohn
problems. This new method relies on
the construction of a polynomial sequence
, , such that
quadratically converges to whenever the starting polynomial
has
zeros with positive real parts and
zeros with negative real parts.
By combining some
new results
on structured matrices with the fast polynomial arithmetic, we prove that the
coefficients of can be computed
starting from the coefficients of
at the computational cost of
arithmetical operations.
Moreover, by means of numerical experiments, we show that the bit precision of
computations suffices to support the stated computational properties.
In this way, apart from
a logarithmic factor, we arrive at the current best upper bound of for the
bit complexity of the mentioned stability problems
Computing a Hurwitz factorization of a polynomial
No full textAbstractA polynomial is called a Hurwitz polynomial (sometimes, when the coefficients are real, a stable polynomial) if all its roots have real part strictly less than zero. In this paper we present a numerical method for computing the coefficients of the Hurwitz factor f(z) of a polynomial p(z). It is based on a polynomial description of the classical LR algorithm for solving the matrix eigenvalue problem. Similarly with the matrix iteration, it turns out that the proposed scheme has a global linear convergence and, moreover, the convergence rate can be improved by considering the technique of shifting. Our numerical experiments, performed with several test polynomials, indicate that the algorithm has good stability properties since the computed approximation errors are generally in accordance with the estimated condition numbers of the desired factors
POLYNOMIAL ROOT COMPUTATION BY MEANS OF THE LR ALGORITHM
No full textBy representing the algorithm of Rutishauser and its variants in a
polynomial setting, we derive
numerical methods for approximating either all of the roots
or a number of the roots of minimum modulus
of a given polynomial of degree . These methods share the
convergence properties of the matrix iteration but, unlike it,
they
can be arranged to produce parallel and sequential
algorithms which are highly efficient
expecially in the case where
Computationally efficient applications of the Euclidean algorithm to zero location
No full textAbstractWe characterize the inertia of the n × n Hankel matrix associated with a pair of real polynomials in terms of the quotients generated by the Euclidean algorithm applied to these polynomials. In this way, we solve certain classical zero-location problems at the computational cost of O(n2) arithmetic operations, which can be reduced to O(n log2 n) if fast polynomial arithmetic is used
A Fast Algorithm for Generalized Hankel Matrices Arising in Finite Moment Problems
No full textAbstractConsider an n × n lower triangular matrix L whose (i + 1)st row is defined by the coefficients of the real polynomial pi(x) of degree i such that {pi(x)} is a set of orthogonal polynomials satisfying a standard three-term recurrence relation. If H is an n × n real Hankel matrix with nonsingular leading principal submatrices, then Ĥ = LHLT will be referred to as a strongly nonsingular Hankel matrix with respect to the orthogonal polynomial basis {pi(x)}. In this paper we develop an efficient O(n2) algorithm for the solution of a system of linear equations with a real symmetric coefficient matrix Ĥ which is a Hankel matrix with respect to a suitable orthogonal polynomial basis. This leads to an efficient method for computing polynomial approximations of an unknown function given its modified moments
Schur Complements of Bezoutians with Application to the Inversion of Block Hankel and Toeplitz Matrices
No full text
- …
