Mathematics

Permanent URI for this community

https://testres.nu.edu.kz/handle/123456789/511

Browse

Browsing Mathematics by Author "Aurentz, Jared L."

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    Fast and backward stable computation of roots of polynomials
    (SIAM Journal on Matrix Analysis and Applications, 2015) Aurentz, Jared L.; Mach, Thomas; Vandebril, Raf; Watkins, David S.
    A stable algorithm to compute the roots of polynomials is presented. The roots are found by computing the eigenvalues of the associated companion matrix by Francis's implicitly shifted QR algorithm. A companion matrix is an upper Hessenberg matrix that is unitary-plus-rankone, that is, it is the sum of a unitary matrix and a rank-one matrix. These properties are preserved by iterations of Francis's algorithm, and it is these properties that are exploited here. The matrix is represented as a product of 3n - 1 Givens rotators plus the rank-one part, so only O(n) storage space is required. In fact, the information about the rank-one part is also encoded in the rotators, so it is not necessary to store the rank-one part explicitly. Francis's algorithm implemented on this representation requires only O(n) flops per iteration and thus O(n2) flops overall. The algorithm is described, normwise backward stability is proved, and an extensive set of numerical experiments is presented. The algorithm is shown to be about as accurate as the (slow) Francis QR algorithm applied to the companion matrix without exploiting the structure. It is faster than other fast methods that have been proposed, and its accuracy is comparable or better.
  • Thumbnail Image
    ItemOpen Access
    Fast and stable unitary QR algorithm
    (Electronic Transactions on Numerical Analysis, 2015) Aurentz, Jared L.; Mach, Thomas; Vandebril, Raf; Watkins, David S.
    A fast Fortran implementation of a variant of Gragg's unitary Hessenberg QR algorithm is presented. It is proved, moreover, that all QR- And QZ-like algorithms for the unitary eigenvalue problems are equivalent. The algorithm is backward stable. Numerical experiments are presented that confirm the backward stability and compare the speed and accuracy of this algorithm with other methods.
  • Thumbnail Image
    ItemOpen Access
    Roots of Polynomials: on twisted QR methods for companion matrices and pencils
    (arXiv, 2016-11-08) Aurentz, Jared L.; Mach, Thomas; Robol, Leonardo; Vandebril, Raf; Watkins, David S.
    Two generalizations of the companion QR algorithm by J.L. Aurentz, T. Mach, R. Vandebril, and D.S. Watkins, SIAM Journal on Matrix Analysis and Applications, 36(3): 942--973, 2015, to compute the roots of a polynomial are presented. First, we will show how the fast and backward stable QR algorithm for companion matrices can be generalized to a QZ algorithm for companion pencils. Companion pencils admit a greater flexibility in scaling the polynomial and distributing the matrix coefficients over both matrices in the pencil. This allows for an enhanced stability for polynomials with largely varying coefficients. Second, we will generalize the pencil approach further to a twisted QZ algorithm. Whereas in the classical QZ case Krylov spaces govern the convergence, the convergence of the twisted case is determined by a rational Krylov space. A backward error analysis to map the error back to the original pencil and to the polynomial coefficients shows that in both cases the error scales quadratically with the input. An extensive set of numerical experiments supports the theoretical backward error, confirms the numerical stability and shows that the computing time depends quadratically on the problem size.