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

BIDIRECTIONAL CHASING algorithmS FOR THE EIGENVALUE PROBLEM

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1993年第1期14卷 166-179页

作者： WATKINS, DS

The qr eigenvalue algorithm and its variants are usually implemented implicitly as chasing algorithms. The matrix whose eigenvalues are sought is first reduced to Hessenberg form by a similarity transformation, then the chasing iterations are begun. Each iteration is a sequence of similarity transformations that create a bulge in the Hessenberg form at one corner of the matrix, then chase the bulge along the diagonal to the opposite corner and finally off the edge of the matrix. Byers's Hamiltonian qr algorithm is an example of a chasing algorithm that has a special feature. In order to preserve the Hamiltonian structure of the matrices, the algorithm forms and chases two bulges simultaneously. Viewed in the appropriate coordinate system, this process can be seen as one in which two bulges are created at opposite comers of the matrix and chased toward each other. They collide in the middle, they interact, and then they continue to the corners of the matrix, where they vanish. In this paper it is shown that the single-shift Hamiltonian qr algorithm is just one of a family of bidirectional chasing algorithms that can be applied to arbitrary matrices. Thus the basic mechanism underlying the Hamiltonian qr algorithm does not rely on the Hamiltonian structure in any way. The structure is exploited to make the algorithm more efficient and to improve its numerical stability.

关键词： EIGENVALUE qr algorithm GR algorithm CHASING THE BULGE HAMILTONIAN MATRIX

来源：评论

学校读者我要写书评

暂无评论

qr-LIKE algorithmS FOR THE NONSYMMETRIC EIGENVALUE PROBLEM

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 1993年第3期19卷 407-418页

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

Hybrid codes that combine elements of the qr and LR algorithms are described. The codes can calculate the eigenvalues and, optionally, eigenvectors of real, nonsymmetric matrices. Extensive tests are presented as evidence that, for certain choices of parameters, the hybrid codes possess the same high reliability as the qr algorithm and are significantly faster. The greatest success has been achieved with the codes that calculate eigenvalues only. These can do the task in 15% to 50% less time than the qr algorithm.

关键词： algorithmS PERFORMANCE CHASING THE BULGE EIGENVALUE EIGENVECTOR GR algorithm LR algorithm qr algorithm

来源：评论

学校读者我要写书评

暂无评论

qr-LIKE algorithmS FOR SYMMETRICAL ARROW MATRICES

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1992年第2期13卷 655-658页

作者： ARBENZ, P GOLUB, GH STANFORD UNIV DEPT COMP SCI STANFORD CA 94305 USA

It is shown that no qr-like algorithm exists for symmetric arrow matrices, i.e., for matrices whose elements vanish, except those on the diagonal and in the first row and column.

关键词： qr algorithm ARROW MATRIX BORDERED DIAGONAL MATRIX

来源：评论

学校读者我要写书评

暂无评论

IMPLICIT SHIFTING IN THE qr AND RELATED algorithmS

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1991年第2期12卷 385-400页

作者： MIMINIS, GS PAIGE, CC MCGILL UNIV SCH COMP SCIMONTREAL H3A 2A7QUEBECCANADA

A new approach is suggested for deriving the theory of implicit shifting in the qr algorithm applied to a Hessenberg matrix. This is less concise than Francis' original approach ([Comput. J., 4(1961), pp. 265-271], [Comput. J., 4(1962), pp. 332-345]) but is more instructive, and extends easily to more general cases. For example, it enables us to design implicitly shifted qr algorithms for band and block Hessenberg matrices. It can also be applied to related algorithms such as the LR algorithm, and to algorithms which do not produce triangular matrices in the factorization step. The approach provides details that can be useful in designing numerically effective algorithms in various areas. In addition to the above, the standard theory describing the result of the qr algorithm with k shifts on a Hessenberg matrix A is extended to the case where some of the shifts can be eigenvalues. This has a practical value in special cases such as eigenvalue allocation. The extension is given for both the explicitly and implicitly shifted qr algorithms, and shows to what extent the latter mimics the former. The new approach to the theory again handles the implicit case simply and clearly.

关键词： MATRIX EIGENPROBLEM IMPLICIT SHIFT qr algorithm POLE PLACEMENT

来源：评论

学校读者我要写书评

暂无评论

THE BIDIAGONAL SINGULAR VALUE DECOMPOSITION AND HAMILTONIAN-MECHANICS

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 1991年第5期28卷 1463-1516页

作者： DEIFT, P DEMMEL, J LI, LC TOMEI, C PENN STATE UNIV DEPT MATHUNIVERSITY PKPA 16802 PONTIFICIA UNIV CATOLICA RIO DE JANEIRO BR-20000 RIO DE JANEIROBRAZIL

Computing the singular value decomposition of a bidiagonal matrix B is considered. This problem arises in the singular value decomposition of a general matrix, and in the eigenproblem for a symmetric positive-definite tridiagonal matrix. It is shown that if the entries of B are known with high relative accuracy, the singular values and singular vectors of B will be determined to much higher accuracy than the standard perturbation theory suggests. It is also shown that the algorithm in [Demmel and Kahan, SIAM J. Sci. Statist. Comput., 11 (1990), pp. 873-912] computes the singular vectors as well as the singular values to this accuracy. A Hamiltonian interpretation of the algorithm is also given, and differential equation methods are used to prove many of the basic facts. The Hamiltonian approach suggests a way to use flows to predict the accumulation of error in other eigenvalue algorithms as well.

关键词： SINGULAR VALUE DECOMPOSITION qr algorithm HAMILTONIAN FLOW

来源：评论

学校读者我要写书评

暂无评论

CHASING algorithmS FOR THE EIGENVALUE PROBLEM

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1991年第2期12卷 374-384页

作者： WATKINS, DS ELSNER, L UNIV BIELEFELD FAK MATHW-4800 BIELEFELD 1GERMANY

A generic chasing algorithm for the matrix eigenvalue problem is introduced and studied. This algorithm includes, as special cases, the implicit, multiple-step qr and LR algorithms and similar bulge-chasing algorithms for the standard eigenvalue problem. The scope of the generic chasing algorithm is quite broad;it encompasses a number of chasing algorithms that cannot be analyzed by the traditional (e.g., implicit Q theorem) approach. These include the LR algorithm with partial pivoting and other chasing algorithms that employ pivoting for stability, as well as hybrid algorithms that combine elements of the LR and qr algorithms. The main result is that each step of the generic chasing algorithm amounts to one step of the generic GR algorithm. Therefore the convergence theorems for GR algorithms that were proven in a previous work [D. S. Watkins and L. Elsner, Linear Algebra Appl., 143 (1991), pp. 19-47] also apply to the generic chasing algorithm.

关键词： EIGENVALUE qr algorithm GR algorithm CHASING THE BULGE SUBSPACE ITERATION

来源：评论

学校读者我要写书评

暂无评论

ON RUTISHAUSER APPROACH TO SELF-SIMILAR FLOWS

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1990年第2期11卷 301-311页

作者： WATKINS, DS ELSNER, L UNIV BIELEFELD FAK MATHW-4800 BIELEFELD 1GERMANY

Certain variants of the Toda flow are continuous analogues of the $qr$ algorithm and other algorithms for calculating eigenvalues of matrices. This was a remarkable discovery of the early eighties. Until very recently contemporary researchers studying this circle of ideas have been unaware that continuous analogues of the quotient-difference and $LR$ algorithms were already known to Rutishauser in the fifties. Rutishauser’s continuous analogue of the quotient-difference algorithm contains the finite, nonperiodic Toda flow as a special case. A nice feature of Rutishauser’s approach is that it leads from the (discrete) eigenvalue algorithm to the (continuous) flow by a limiting process. Thus the connection between the algorithm and the flow does not come as a surprise. In this paper it is shown how Rutishauser’s approach can be generalized to yield large families of flows in a natural manner. The flows derived include continuous analogues of the $LR$, $qr$, $SR$, and $HR$ algorithms.

关键词： 15A18 15A23 58F19 58F25 65F15 Toda flow self-similar flow quotient-difference algorithm LR algorithm qr algorithm

来源：评论

学校读者我要写书评

暂无评论

SELF-EQUIVALENT FLOWS ASSOCIATED WITH THE SINGULAR VALUE DECOMPOSITION: 收藏
分享
引用; SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1989年第2期10卷 244-258页; 作者： WATKINS, DS ELSNER, L UNIV BIELEFELD FAK MATHD-4800 BIELEFELD 1FED REP GER; A family of flows which are continuous analogues of the constant and variable shift qrqrqr algorithms for the singular value decomposition problem is presented, and it is shown that certain of these flows interpolate ... 详细信息; A family of flows which are continuous analogues of the constant and variable shift $<span style = 'color:red'>qr</span>$ algorithms for the singular value decomposition problem is presented, and it is shown that certain of these flows interpolate the $Q R$; 来源：评论; 学校读者我要写书评

暂无评论

ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT qr ITERATION

引用

International Journal of High Speed Computing 1989年第1期1卷 97-112页

作者： Zhaojun Bai James Demmel Courant Institute of Mathematical Sciences New York University 251 Mercer Street New York NY 10012 USA

The usual qr algorithm for finding the eigenvalues of a Hessenberg matrix H is based on vector-vector operations, e.g. adding a multiple of one row to another. The opportunities for parallelism in such an algorithm are limited. In this paper, we describe a reorganization of the qr algorithm to permit either matrix-vector or matrix-matrix operations to be performed, both of which yield more efficient implementations on vector and parallel machines. The idea is to chase a k by k bulge rather than a 1 by 1 or 2 by 2 bulge as in the standard qr algorithm. We report our preliminary numerical experiments on the CONVEX C-1 and CYBER 205 vector machines.

关键词： Eigenvalue Hessenberg matrix qr algorithm BLAS Parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

THE GENERALIZED EIGENPROBLEM - POLE-ZERO COMPUTATION

引用

PROCEEDINGS OF THE IEEE 1988年第2期76卷 103-120页

作者： HALEY, SB Dept. of Electr. & Comput. Sci. California Univ. Davis CA

A modification-decomposition (MD) method is used to compute linear system transfer function poles and zeros by transforming an N-dimensional generalized eigenvalue problem to an M-dimensional standard eigenvalue problem with M⩾ r, where r is the lesser of the ranks of the dynamic or nondynamic component matrix of the system. Hence, network eigenvalue problems normally solved by applying the QZ algorithm directly, or after deflation preprocessing, are solvable with the more efficient qr algorithm. It is shown that the flop (floating-point operations) count for MD-qr algorithms is always less than the flop count for the most efficient deflation-QZ algorithms. For r⩽N, the MD-qr algorithms are exceptionally efficient. Using a parameter matrix decomposition of the dynamic or nondynamic component matrix, the MD method gives physical insight, and it provides a general proof of manifold constraints relating network time constants and poles and zeros. From these relations, accurate dominant and subdominant pole approximations are derived. A general eigenvalue sensitivity formula and a very flexible method for computing eigenvectors is developed and applied to pole sensitivity computation

关键词： M-dimensional standard eigenvalue problem MD-qr algorithms N-dimensional generalized eigenvalue problem qr algorithm circuit analysis circuit analysis computing computational complexity compute linear system transfer function poles and zeros flexible method for computing eigenvectors floating-point operations general eigenvalue sensitivity formula general proof of manifold constraints generalized eigenproblem matrix algebra matrix algebra modification decomposition method network eigenvalue problems network time constants parameter matrix decomposition physical insight pole sensitivity computation pole-zero computation poles and zeros poles and zeros

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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