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

Restructuring the Tridiagonal and Bidiagonal qr algorithms for Performance

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2014年第3期40卷 18-18页

作者： van Zee, Field G. van de Geijn, Robert A. Quintana-Orti, Gregorio Univ Texas Austin Inst Computat Engn & Sci Dept Comp Sci Austin TX 78712 USA Univ Jaume 1 Dept Ingn & Ciencia Comp Castellon de La Plana 12071 Spain

We show how both the tridiagonal and bidiagonal qr algorithms can be restructured so that they become rich in operations that can achieve near-peak performance on a modern processor. The key is a novel, cache-friendly algorithm for applying multiple sets of Givens rotations to the eigenvector/singular vector matrix. This algorithm is then implemented with optimizations that: (1) leverage vector instruction units to increase floating-point throughput, and (2) fuse multiple rotations to decrease the total number of memory operations. We demonstrate the merits of these new qr algorithms for computing the Hermitian eigenvalue decomposition (EVD) and singular value decomposition (SVD) of dense matrices when all eigenvectors/ singular vectors are computed. The approach yields vastly improved performance relative to traditional qr algorithms for these problems and is competitive with two commonly used alternatives-Cuppen's Divide-and-Conquer algorithm and the method of Multiple Relatively Robust Representations-while inheriting the more modest O(n) workspace requirements of the original qr algorithms. Since the computations performed by the restructured algorithms remain essentially identical to those performed by the original methods, robust numerical properties are preserved.

关键词： algorithms Performance Eigenvalues singular values tridiagonal bidiagonal EVD SVD qr algorithm Givens rotations linear algebra libraries high performance

来源：评论

学校读者我要写书评

暂无评论

qr-like algorithms for eigenvalue problems

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2000年第1-2期123卷 67-83页

作者： Watkins, DS Washington State Univ Dept Math Pullman WA 99164 USA

In the year 2000 the dominant method for solving matrix eigenvalue problems is still the qr algorithm. This paper discusses the family of GR algorithms, with emphasis on the qr algorithm. Included are historical remarks, an outline of what GR algorithms are and why they work, and descriptions of the latest, highly parallelizable, versions of the qr algorithm. Now that we know how to parallelize it, the qr algorithm seems likely to retain its dominance for many years to come. (C) 2000 Elsevier Science B.V. All rights reserved. MSC: 65F15.

关键词： eigenvalue qr algorithm GR algorithm

来源：评论

学校读者我要写书评

暂无评论

Comparison of BR and qr eigenvalue algorithms system small signal stability analysis

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2006年第4期21卷 1848-1855页

作者： Ma, Jian Dong, Zhao Yang Zhang, Pei Univ Queensland Sch Informat Technol & Elect Engn Brisbane Qld 4072 Australia EPRI Palo Alto CA 94304 USA

The BR algorithm is a novel and efficient method to find all eigenvalues of upper Hessenberg matrices and has never been applied to eigenanalysis for power system small signal stability. This paper analyzes differences between the BR and the qr algorithms with performance comparison in terms of CPU time based on stopping criteria and storage requirement. The BR algorithm utilizes accelerating strategies to improve its performance when computing eigenvalues of narrowly banded, nearly tridiagonal upper Hessenberg matrices. These strategies significantly reduce the computation time at a reasonable level of precision. Compared with the qr algorithm, the BR algorithm requires fewer iteration steps and less storage space without depriving of appropriate precision in solving eigenvalue problems of large-scale power systems. Numerical examples demonstrate the efficiency of the BR algorithm in pursuing eigenanalysis tasks of 39-, 68-, 115-, 300-, and 600-bus systems. Experiment results suggest that the BR algorithm is a more efficient algorithm for large-scale power system small signal stability eigenanalysis.

关键词： BR algorithm CPU time eigenvalue calculation power systems qr algorithm small signal stability stopping criteria upper Hessenberg matrix

来源：评论

学校读者我要写书评

暂无评论

Reachable matrices by a qr step with shift

引用

SIAM JOURNAL ON APPLIED DYNAMICAL SYSTEMS 2006年第1期5卷 91-107页

作者： Chu, DL Chu, M Natl Univ Singapore Dept Math Singapore 117543 Singapore N Carolina State Univ Dept Math Raleigh NC 27695 USA

One of the most interesting dynamical systems used in numerical analysis is the qr algorithm. An added maneuver to improve the convergence behavior is the qr iteration with shift which is of fundamental importance in eigenvalue computation. This paper is a theoretical study of the set of all isospectral matrices "reachable" by the dynamics of the qr algorithm with shift. A matrix B is said to be reachable by A if B = RQ + mu I, where A - mu I = qr is the qr decomposition for some mu is an element of R. It is proved that in general the qr algorithm with shift is neither reflexive nor symmetric. Examples are given to demonstrate that this relation is neither transitive nor antisymmetric. It is further discovered that the reachable set from a given n x n matrix A forms 2(n-1) disjoint open loops if n is even and 2(n-2) disjoint components each of which is no longer a loop when n is odd.

关键词： qr algorithm shift analytic qr decomposition reachable matrices reflexivity symmetry transitivity

来源：评论

学校读者我要写书评

暂无评论

A quadratically convergent qr-like method without shifts for the Hermitian eigenvalue problem

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2006年第2-3期417卷 478-495页

作者： Zha, Hongyuan Zhang, Zhenyue Ying, Wenlong Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA

We propose a new qr-like algorithm, symmetric squared qr (SSqr) method, that can be readily parallelized using commonly available parallel computational primitives such as matrix-matrix multiplication and qr decomposition. The algorithm converges quadratically and the quadratic convergence is achieved through a squaring technique without utilizing any kind of shifts. We provide a rigorous convergence analysis of SSqr and derive structures for several of the important quantities generated by the algorithm. We also discuss various practical implementation issues such as stopping criteria and deflation techniques. We demonstrate the convergence behavior of SSqr using several numerical examples. (c) 2005 Elsevier Inc. All rights reserved.

关键词： eigenvalue problem qr algorithm Hermitian matrix convergence analysis

来源：评论

学校读者我要写书评

暂无评论

The relation between the qr and LR algorithms

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1998年第2期19卷 551-555页

作者： Xu, HG Fudan Univ Dept Math Shanghai 200433 Peoples R China

For an Hermitian matrix the qr transform is diagonally similar to two steps of the LR transforms. Even for non-Hermitian matrices the qr transform may be written in rational form.

关键词： qr algorithm LR algorithm triangular factorization Cholesky factorization

来源：评论

学校读者我要写书评

暂无评论

Bulge exchanges in algorithms of qr type

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1998年第4期19卷 1074-1096页

作者： Watkins, DS Washington State Univ Dept Pure & Appl Math Pullman WA 99164 USA

The qr algorithm and its variants are among the most popular methods for calculating eigenvalues of matrices. Typical implementations chase bulges from top to bottom of an upper Hessenberg matrix. It is also possible to chase bulges from bottom to top. There are some situations in which it may be advantageous to chase bulges in both directions at once, in which case one needs a procedure for passing bulges through each other without mixing up the information that the bulges convey. This paper derives a procedure for passing bulges of arbitrary degree through each other. Experiments with a Fortran 90 program show that the procedure works well in practice for bulges of degree two.

关键词： eigenvalue computation qr algorithm bulge exchanges

来源：评论

学校读者我要写书评

暂无评论

Full Symmetric Toda System: Solution via qr-Decomposition

引用

FUNCTIONAL ANALYSIS AND ITS APPLICATIONS 2023年第4期57卷 346-363页

作者： Talalaev, D. V. Chernyakov, Yu. B. Sharygin, G. I. Kurchatov Inst Natl Res Ctr Moscow Russia Lomonosov Moscow State Univ Moscow Russia PG Demidov Yaroslavl State Univ Yaroslavl Russia Natl Res Univ Moscow Inst Phys & Technol Moscow 141701 Russia Russian Acad Sci Inst Informat Transmiss Problems Kharkevich Inst Moscow Russia

The full symmetric Toda system is a generalization of the open Toda chain, for which the Lax operator is a symmetric matrix of general form. This system is Liouville integrable and even superintegrable. Deift, Lee, Nando, and Tomei (DLNT) proposed the chopping method for constructing integrals of such a system. In the paper, a solution of Hamiltonian equations for the entire family of DLNT integrals is constructed by using the generalized qr factorization method. For this purpose, certain tensor operations on the space of Lax operators and special differential operators on the Lie algebra are introduced. Both tools can be interpreted in terms of the representation theory of the Lie algebra sl(n) and are expected to generalize to arbitrary real semisimple Lie algebras. As is known, the full Toda system can be interpreted in terms of a compact Lie group and a flag space. Hopefully, the results on the trajectories of this system obtained in the paper will be useful in studying the geometry of flag spaces.

关键词： full Toda system qr algorithm flag space noncommutative integrability

来源：评论

学校读者我要写书评

暂无评论

qr methods and error analysis for computing Lyapunov and Sacker-Sell spectral intervals for linear differential-algebraic equations

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2011年第2-4期35卷 281-322页

作者： Vu Hoang Linh Mehrmann, Volker Van Vleck, Erik S. Tech Univ Berlin Inst Math D-10623 Berlin Germany Vietnam Natl Univ Fac Math Mech & Informat Hanoi Vietnam Univ Kansas Dept Math Lawrence KS 66045 USA

In this paper, we propose and investigate numerical methods based on qr factorization for computing all or some Lyapunov or Sacker-Sell spectral intervals for linear differential-algebraic equations. Furthermore, a perturbation and error analysis for these methods is presented. We investigate how errors in the data and in the numerical integration affect the accuracy of the approximate spectral intervals. Although we need to integrate numerically some differential-algebraic systems on usually very long time-intervals, under certain assumptions, it is shown that the error of the computed spectral intervals can be controlled by the local error of numerical integration and the error in solving the algebraic constraint. Some numerical examples are presented to illustrate the theoretical results.

关键词： Differential-algebraic equation Strangeness index Lyapunov exponent Sacker-Sell spectrum Exponential dichotomy Spectral interval Smooth qr factorization qr algorithm Kinematic equivalence Steklov function

来源：评论

学校读者我要写书评

暂无评论

DEFERRED SHIFTING SCHEMES FOR PARALLEL qr METHODS

引用

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

作者： VANDEGEIJN, RA

Parallel implementation of the qr algorithm for solving the symmetric eigenvalue problem requires more than a straightforward transcription of sequential code to parallel code. Experimental adjustments include new shifting techniques and omission of the initial reducing to upper Hessenberg form. In this paper, the theory of the convergence of algorithms of decomposition type for the algebraic eigenvalue problem developed by Watkins and Elsner is generalized. The results are extended to deferred shifting schemes, which allow pipelining of iterations in parallel implementations, and analyzing the deterioration of the convergence rate. Furthermore, it is shown that eigenvalues need not be simple to obtain quadratic convergence for nondefective nonsymmetric matrices and cubic convergence for symmetric matrices.

关键词： CONVERGENCE EIGENVALUE PARALLEL COMPUTING qr algorithm SCHUR DECOMPOSITION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：