1,721,079 research outputs found
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
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
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
Schur Complements of Bezoutians with Application to the Inversion of Block Hankel and Toeplitz Matrices
No full text
A unitary Hessenberg QR-based algorithm via semiseparable matrices
No full textAbstractIn this paper, we present a novel method for solving the unitary Hessenberg eigenvalue problem. In the first phase, an algorithm is designed to transform the unitary matrix into a diagonal-plus-semiseparable form. Then we rely on our earlier adaptation of the QR algorithm to solve the dpss eigenvalue problem in a fast and robust way. Exploiting the structure of the problem enables us to yield a quadratic time using a linear memory space. Nonetheless the algorithm remains robust and converges as fast as the customary QR algorithm. Numerical experiments confirm the effectiveness and the robustness of our approach
Accurate polynomial root-finding methods for symmetric tridiagonal matrix eigenproblems
Full text linkIn this paper we consider the application of polynomial root-finding methods to the
solution of the tridiagonal matrix eigenproblem. All considered solvers are based on evaluating the Newton correction. We show that the use of scaled three-term recurrence relations complemented with error free transformations yields some compensated schemes which significantly improve the accuracy of computed results at a modest increase in computational cost. Numerical experiments illustrate that under some restriction on the conditioning the novel iterations can approximate and/or refine the eigenvalues of a tridiagonal matrix with high relative accuracy
- …
