检索结果-内蒙古大学图书馆

Eigenvalue condition numbers and pseudospectra of Fiedler matrices

CALCOLO 2017年第1期54卷 319-365页

作者： De Teran, Fernando Dopico, Froilan M. Perez, Javier Univ Carlos III Madrid Dept Math Ave Univ 30 Leganes 28911 Spain Univ Manchester Sch Math Oxford Rd Manchester M13 9PL Lancs England

The aim of the present paper is to analyze the behavior of Fiedler companion matrices in the polynomial root-finding problem from the point of view of conditioning of eigenvalues. More precisely, we compare: (a) the condition number of a given root of a monic polynomial p(z) with the condition number of as an eigenvalue of any Fiedler matrix of p(z), (b) the condition number of as an eigenvalue of an arbitrary Fiedler matrix with the condition number of as an eigenvalue of the classical Frobenius companion matrices, and (c) the pseudozero sets of p(z) and the pseudospectra of any Fiedler matrix of p(z). We prove that, if the coefficients of the polynomial p(z) are not too large and not all close to zero, then the conditioning of any root of p(z) is similar to the conditioning of as an eigenvalue of any Fiedler matrix of p(z). On the contrary, when p(z) has some large coefficients, or they are all close to zero, the conditioning of as an eigenvalue of any Fiedler matrix can be arbitrarily much larger than its conditioning as a root of p(z) and, moreover, when p(z) has some large coefficients there can be two different Fiedler matrices such that the ratio between the condition numbers of as an eigenvalue of these two matrices can be arbitrarily large. Finally, we relate asymptotically the pseudozero sets of p(z) with the pseudospectra of any given Fiedler matrix of p(z), and the pseudospectra of any two Fiedler matrices of p(z).

关键词： Roots of polynomials Eigenvalues Companion matrices qr algorithm Fiedler matrices Conditioning Pseudospectrum Pseudozero sets of polynomials

来源：评论

学校读者我要写书评

暂无评论

FAST AND BACKWARD STABLE COMPUTATION OF ROOTS OF POLYNOMIALS, PART II: BACKWARD ERROR ANALYSIS;COMPANION MATRIX AND COMPANION PENCIL

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2018年第3期39卷 1245-1269页

作者： Aurentz, Jared L. Mach, Thomas Robol, Leonardo Vandebril, Raf Watkins, David S. Univ Autonoma Madrid Inst Ciencias Matemat E-28049 Madrid Spain Nazarbayev Univ Sch Sci & Technol Dept Math Astana 010000 Kazakhstan CNR Ist Sci & Tecnol Informaz A Faedo ISTI I-56127 Pisa Italy Univ Leuven KU Leuven Dept Comp Sci B-3001 Leuven Belgium Washington State Univ Dept Math Pullman WA 99164 USA

This work is a continuation of work by J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, J. Matrix Anal. Appi., 36 (2015), pp. 942-973]. In that paper we introduced a companion qr algorithm that finds the roots of a polynomial by computing the eigenvalues of the companion matrix in O(n(2)) time using O(n) memory. We proved that the method is backward stable. Here we introduce, as an alternative, a companion QZ algorithm that solves a generalized eigenvalue problem for a companion pencil. More importantly, we provide an improved backward error analysis that: takes advantage of the special structure of the problem. The improvement: is also due, in part, to an improvement in the accuracy (in both theory and practice) of the turnover operation, which is the key component of our algorithms. We prove that for the companion qr algorithm, the backward error on the polynomial coefficients varies linearly with the norm of the polynomial's vector of coefficients. Thus, the companion qr. algorithm has a smaller backward error than the unstructured qr algorithm (used by MATLAB's roots command, for example), for which the backward error on the polynomial coefficients grows quadratically with the norm of the coefficient vector. The companion QZ algorithm has the same favorable backward error as companion qr, provided that the polynomial coefficients are properly scaled.

关键词： polynomial root companion matrix companion pencil eigenvalue Francis algorithm qr algorithm QZ algorithm core transformation backward stability

来源：评论

学校读者我要写书评

暂无评论

FAST AND BACKWARD STABLE COMPUTATION OF ROOTS OF POLYNOMIALS

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2015年第3期36卷 942-973页

作者： Aurentz, Jared L. Mach, Thomas Vandebril, Raf Watkins, David S. Univ Oxford Math Inst Oxford OX2 6GG England Katholieke Univ Leuven Dept Comp Sci B-3001 Heverlee Belgium Washington State Univ Dept Math Pullman WA 99164 USA

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(n(2)) 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.

关键词： polynomial root rootfinding companion matrix eigenvalue qr algorithm rotators

来源：评论

学校读者我要写书评

暂无评论

Using level 3 BLAS in rotation-based algorithms

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1998年第2期19卷 626-634页

作者： Lang, B Berg Univ Wuppertal Fachbereich Math D-42097 Wuppertal Germany

This paper presents a technique that allows using level 3 BLAS in a number of rotation-based algorithms. In particular, the update of an orthogonal transformation matrix which often involves the vast majority of operations can be done with a matrix-matrix product. As a case study, the technique is applied to the qr and QL algorithms for computing the eigensystem of a symmetric tridiagonal matrix. The modifications do not affect the convergence properties of the algorithms nor do they significantly increase the overall number of operations. Thus, the computations can be sped up by more than 50% on machines with a distinct memory hierarchy, like the Intel i860 or IBM RS/6000, provided the block size is set appropriately. We also present a simple theoretical analysis that allows selecting an almost-optimal block size.

关键词： BLAS 3 rotation qr algorithm performance modeling

来源：评论

学校读者我要写书评

暂无评论

An Empirical Comparison of Encoding algorithms of the Low Density Parity Check Code for Decode and Forward Protocol Relay System

引用

WIRELESS PERSONAL COMMUNICATIONS 2021年第3期117卷 2007-2026页

作者： Jamaah, S. Hushairi, Z. Al-Khalid, O. Khairuddin, A. H. Univ Malaysia Sarawak Fac Engn Sarawak Malaysia

Decode and a forward (DF) protocol relay technique in cooperative communication is becoming a more attractive method to achieve a higher throughput requirement for wireless communication these days. But the high complexity operation is a major issue in the DF protocol relay processing system. The encoding operation which is a pre-processing stage of the decoding process consumes high complexity in the DF protocol relay system. Thus, it is important to tackle the encoding operation to ensure low complexity and good performance of the subsequent decoding operation in the DF protocol relay system. Thus far, very limited works have been reported on identifying a suitable encoding algorithm of encoding operation for the DF protocol relay system using the Low Density Parity Check (LDPC) code. In this paper, we present a suitable encoding algorithm for the DF protocol relay system using the LDPC code. To find out the most suitable encoding algorithm for the DF protocol relay system using LDPC code, we introduce the LDPC code encoding model. Eight different encoding algorithms based on Lower Upper and Orthogonal Upper algorithms presented in the LDPC code encoding model. The encoding execution time, the number of nonzero, and the pattern of nonzero was used to evaluate the computational complexity performance of the designed LDPC code encoding model. The most suitable encoding algorithm for the required criteria of the DF protocol relay system using the LDPC code is identified.

关键词： Cooperative communication Decode and forward Execution time LDPC code LU algorithm qr algorithm

来源：评论

学校读者我要写书评

暂无评论

SOME PERSPECTIVES ON THE EIGENVALUE PROBLEM

引用

SIAM REVIEW 1993年第3期35卷 430-471页

作者： WATKINS, DS WASHINGTON STATE UNIV DEPT PURE & APPL MATH PULLMAN WA 99164 USA

This expository paper explores the relationships among a number of algorithms for solving eigenvalue problems, including the power method, subspace iteration, the qr algorithm, and the Arnoldi and symmetric Lanczos algorithms. The symmetric Lanczos algorithm is shown to be identical to the three-term recursion (Stieltjes procedure) for computing orthogonal polynomials with respect to a measure on the real line. The connection between measures on the line and symmetric tridiagonal (Jacobi) matrices is investigated. If such a matrix is transformed by a step of the qr algorithm, there is a corresponding transformation in the measure. The tridiagonal matrices are also exploited for the construction of Gaussian quadrature formulas for measures on the line. The developments on the real line are replicated with suitable modifications on the unit circle via Lanczos-like procedures for unitary operators. The best-known procedure of this type is the recursion of Szego for computing orthogonal polynomials on the unit circle. The approach taken in this paper is to develop recursions that compute orthogonal Laurent polynomials (rational functions) rather than polynomials. These recursions are then modified to yield the Szego recursion.

关键词： EIGENVALUE INVARIANT SUBSPACE qr algorithm ARNOLDI LANCZOS SELF-ADJOINT UNITARY ORTHOGONAL POLYNOMIALS SPECTRAL THEOREM QUADRATURE

来源：评论

学校读者我要写书评

暂无评论

algorithms for modifying recurrence relations of orthogonal polynomial and rational functions when changing the discrete inner product

引用

APPLIED NUMERICAL MATHEMATICS 2024年 200卷 429-452页

作者： Van Barel, Marc Van Buggenhout, Niel Vandebril, Raf KU Leuven Univ Leuven Dept Comp Sci Celestijnenlaan 200A B-3001 Leuven Belgium Charles Univ Prague Fac Math & Phys Sokolovska 83 Prague 18675 Czech Republic

Often, polynomials or rational functions, orthogonal for a particular inner product are desired. In practical numerical algorithms these polynomials are not constructed, but instead the associated recurrence relations are computed. Moreover, also typically the inner product is changed to a discrete inner product, which is the finite sum of weighted functions evaluated in specific nodes. For particular applications it is beneficial to have an efficient procedure to update the recurrence relations when adding or removing nodes from the inner product. The construction of the recurrence relations is equivalent to computing a structured matrix (polynomial) or pencil (rational) having prescribed spectral properties. Hence the solution of this problem is often referred to as solving an Inverse Eigenvalue Problem. In [34] we proposed updating techniques to add nodes to the inner product while efficiently updating the recurrences. To complete this study we present in this article manners to efficiently downdate the recurrences when removing nodes from the inner product. The link between removing nodes and the qr algorithm to deflate eigenvalues is exploited to develop efficient algorithms. We will base ourselves on the perfect shift strategy and develop algorithms, both for the polynomial case and the rational function setting. Numerical experiments validate our approach. (c) 2023 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： Orthogonal rational functions Orthogonal polynomials Downdating Discrete inner product qr algorithm Perfect shift strategy

来源：评论

学校读者我要写书评

暂无评论

An extended Hessenberg form for Hamiltonian matrices

引用

CALCOLO 2017年第1期54卷 423-453页

作者： Ferranti, Micol Iannazzo, Bruno Mach, Thomas Vandebril, Raf Katholieke Univ Leuven Dept Comp Sci Celestijnenlaan 200A B-3001 Leuven Belgium Univ Perugia Dipartimento Matemat & Informat Via Vanvitelli 1 I-06123 Perugia Italy

A unitary symplectic similarity transformation for a special class of Hamiltonian matrices to extended Hamiltonian Hessenberg form is presented. Whereas the classical Hessenberg form links to Krylov subspaces, the extended Hessenberg form links to extended Krylov subspaces. The presented algorithm generalizes thus the classic reduction to Hamiltonian Hessenberg form and offers more freedom in the choice of Hamiltonian condensed forms, to be used within an extended Hamiltonian qr algorithm. Theoretical results identifying the structure of the extended Hamiltonian Hessenberg form and proofs of uniqueness of the reduction process are included. Numerical experiments confirm the validity of the approach.

关键词： Hamiltonian eigenvalue problems Extended Hessenberg forms qr algorithm

来源：评论

学校读者我要写书评

暂无评论

A NEW ITERATION FOR COMPUTING THE EIGENVALUES OF SEMISEPARABLE (PLUS DIAGONAL) MATRICES

引用

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2008年 33卷 126-150页

作者： Vandebril, Raf Van Barel, Marc Mastronardi, Nicola Katholieke Univ Leuven Dept Comp Wetenschappen Louvain Belgium Ist Applicaz Calcolo M Picone Sez Bari Bari Italy

This paper proposes a new type of iteration for computing eigenvalues of semiseparable (plus diagonal) matrices based on a structured-rank factorization. Remarks on higher order semiseparability ranks are also made. More precisely, instead of the traditional qr iteration, a QH iteration is used. The QH factorization is characterized by a unitary matrix Q and a Hessenberg-like matrix H in which the lower triangular part is semiseparable (often called a lower semiseparable matrix). The Q factor of this factorization determines the similarity transformation of the QH method. It is shown that this iteration is extremely useful for computing the eigenvalues of structured-rank matrices. Whereas the traditional qr method applied to semiseparable (plus diagonal) and Hessenberg-like matrices uses similarity transformations involving 2p(n-1) Givens transformations (where p denotes the semiseparability rank), the QH iteration only needs p(n-1) Givens transformations, which is comparable to the generalized Hessenberg (symmetric band) situation having p subdiagonals. It is also shown that this method can in some sense be interpreted as an extension of the traditional qr method for Hessenberg matrices, i.e., the traditional case also fits into this framework. It is also shown that this iteration exhibits an extra type of convergence behavior compared to the traditional qr method. The algorithm is implemented in an implicit way, based on the Givens-weight representation of the structured rank matrices. Numerical experiments show the viability of this approach. The new approach yields better complexity and more accurate results than the traditional qr method.

关键词： QH algorithm structured rank matrices implicit computations eigenvalue qr algorithm rational qr iteration

来源：评论

学校读者我要写书评

暂无评论

AN EXTENSION OF THE QZ algorithm BEYOND THE HESSENBERG-UPPER TRIANGULAR PENCIL

引用

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2013年 40卷 17-35页

作者： Vandebril, Raf Watkins, David S. Katholieke Univ Leuven Dept Comp Sci B-3001 Heverlee Belgium Washington State Univ Dept Math Pullman WA 99164 USA

Recently, an extension of the class of matrices admitting a Francis type of multishift qr algorithm was proposed by the authors. These so-called condensed matrices admit a storage cost identical to that of the Hessenberg matrix and share all of the properties essential for the development of an effective implicit qr type method. This article continues along this trajectory by discussing the generalized eigenvalue problem. The novelty does not lie in the almost trivial extension of replacing the Hessenberg matrix in the pencil by a condensed matrix, but in the fact that both pencil matrices can be partially of condensed form. Again, the storage cost and crucial features of the Hessenberg-upper triangular pencil are retained, giving rise to an equally viable QZ-like method. The associated implicit algorithm also relies on bulge chasing and exhibits a sort of bulge hopping from one to the other matrix. This article presents the reduction to a condensed pencil form and an extension of the QZ algorithm. Relationships between these new ideas and some known algorithms are also discussed.

关键词： condensed matrices generalized eigenvalues QZ algorithm qr algorithm extended Krylov

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：