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

作者： Amandeep Kaur University of Cambridge

学位级别：硕士

In this thesis we address the analytic and numerical aspects of isospectral flows. Such flows occur in mathematical physics and numerical linear algebra. Their main structural feature is to retain the eigenvalues in the solution space. We explore the solution of Isospectral flows and their stochastic counterpart using explicit generalisation of Magnus expansion. In the first part of the thesis we expand the solution of Bloch–Iserles equa- tions, the matrix ordinary differential system of the form X 0 = [N, X 2 ], t ≥ 0, X(0) = X 0 ∈ Sym(n), N ∈ so(n), where Sym(n) denotes the space of real n × n symmetric matrices and so(n) denotes the Lie algebra of real n × n skew-symmetric matrices. This system is endowed with Poisson structure and is integrable. Various important properties of the flow are discussed. The flow is solved using explicit Magnus expansion and the terms of expansion are represented as binary rooted trees deducing an explicit formalism to construct the trees recursively. Unlike classical numerical methods, e. g. Runge–Kutta and multistep methods, Magnus expansion respects the isospectrality of the system, and the shorthand of binary rooted trees reduces the computational cost of the exponentially growing terms. The desired structure of the solution (also with large time steps) has been displayed. Having seen the promising results in the first part of the thesis, the technique has been extended to the generalised double bracket flow X 0 = [[N, X] + M, X], t ≥ 0, X(0) = X 0 ∈ Sym(n), where N ∈ diag(n) and M ∈ so(n), which is also a form of an Isospectral flow. In the second part of the thesis we define the generalised double bracket flow and discuss its dynamics. It is noted that N = 0 reduces it to an integrable flow, while for M = 0 it results in a gradient flow. We analyse the flow for various non-zero values of N and M by assigning different weights and observe Hopf bifurcation in the system. The discretisation is done using Magnus series and the exp

关键词： Isospectral flow ordinary differential equations eigenvalues Magnus expansion Lie group Lie algebra binary trees Cayley transform double bracket flow Toda lattice qr algorithm Runge–Kutta

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Ortho-diffusion decompositions of graph-based representation of images

引用

PATTERN RECOGNITION 2015年第12期48卷 4097-4115页

作者： Gudivada, Sravan Bors, Adrian G. Univ York Dept Comp Sci York YO10 5GH N Yorkshire England

This paper proposes a new feature representation methodology for graph-based data. Initially, random walks on matrices of pairwise data similarities are considered. A diffusion process is embedded into orthonormal decompositions of such matrices at various scales while enabling a data reduction mechanism as well. At each scale, the qr orthonormal decomposition algorithm, alternating with diffusions and data reduction stages is applied recursively on the given graph-based data representations. The proposed methodology is used in extracting complex feature representations from images, which are then used for image matching and in face recognition. In the face recognition application, both global appearance models and semantic representations of biometric features are considered. Both the correlation and the covariance of images of human faces are considered for the training stage when using global appearance models. The proposed data representation is shown to be robust in face recognition applications, when face images are represented in low resolution and when they are corrupted by noise. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Ortho-diffusion decompositions qr algorithm Face recognition Optical flow estimation

来源：评论

学校读者我要写书评

暂无评论

A new framework for implicit restarting of the Krylov-Schur algorithm

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2015年第2期22卷 220-232页

作者： Bujanovic, Zvonimir Drmac, Zlatko Max Planck Inst Dynam Complex Tech Syst Magdeburg Germany Univ Zagreb Dept Math Zagreb 10000 Croatia

This paper introduces a new framework for implicit restarting of the Krylov-Schur algorithm. It is shown that restarting with arbitrary polynomial filter is possible by reassigning some of the eigenvalues of the Rayleigh quotient through a rank-one correction, implemented using only the elementary transformations (translation and similarity) of the Krylov decomposition. This framework includes the implicitly restarted Arnoldi (IRA) algorithm and the Krylov-Schur algorithm with implicit harmonic restart as special cases. Further, it reveals that the IRA algorithm can be turned into an eigenvalue assignment method. Copyright (c) 2014 John Wiley & Sons, Ltd.

关键词： eigenvalues eigenvalue assignment Arnoldi algorithm Krylov-Schur algorithm implicit restart polynomial filter qr algorithm Rayleigh quotient Ritz values

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The qr algorithm: 50 years later its genesis by John Francis and Vera Kublanovskaya and subsequent developments

引用

IMA JOURNAL OF NUMERICAL ANALYSIS 2009年第3期29卷 467-485页

作者： Golub, Gene Uhlig, Frank Stanford Univ Stanford CA 94305 USA Auburn Univ Dept Math & Stat Auburn AL 36849 USA

Fifty years after the invention of the qr algorithm by John Francis and Vera Kublanovskaya we reconstruct the ideas and the influences that led to its genesis from the originators' own recollections and their sour... 详细信息

关键词： qr algorithm numerical algorithm matrix computation matrix eigenvalue matrix eigenvector Francis Implicit Q Theorem John Francis Vera Kublanovskaya history of math history of computation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A new method for consistency test in fuzzy AHP

引用

JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2013年第2期25卷 457-461页

作者： Mahmoudzadeh, Morteza Bafandeh, Ali R. Islamic Azad Univ East Azarbaijan Sci & Res Branch Dept Management Tabriz Iran Islamic Azad Univ Tabriz Branch Dept Management Tabriz Iran

This paper presents that the consistency test with consideration of a tolerance deviation in fuzzy AHP proposed by L. C. Leung and D. Cao (2000) is not efficient and has some errors, hence a new method of fuzzy consistency test by direct fuzzification of (Quick Response) qr algorithm - which is one of numerical methods for calculating eigenvalues of an arbitrary matrix - has been proposed.

关键词： Fuzzy AHP consistency test qr algorithm genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

FAST COMPUTATION OF THE ZEROS OF A POLYNOMIAL VIA FACTORIZATION OF THE COMPANION MATRIX

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2013年第1期35卷 A255-A269页

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

A new fast algorithm for computing the zeros of a polynomial in O(n(2)) time using O(n) memory is developed. The eigenvalues of the Frobenius companion matrix are computed by applying a nonunitary analogue of Francis's implicitly shifted qr algorithm to a factored form of the matrix. The algorithm achieves high speed and low memory use by preserving the factored form. It also provides a residual and an error estimate for each root. Numerical tests confirm the high speed of the algorithm.

关键词： polynomial root companion matrix qr algorithm

来源：评论

学校读者我要写书评

暂无评论

THE EFFECT OF AGGRESSIVE EARLY DEFLATION ON THE CONVERGENCE OF THE qr algorithm

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2008年第2期30卷 805-821页

作者： Kressner, Daniel Swiss Fed Inst Technol Seminar Angew Math Zurich Switzerland

Aggressive early deflation has proven to significantly enhance the convergence of the qr algorithm for computing the eigenvalues of a nonsymmetric matrix. One purpose of this paper is to point out that this deflation strategy is equivalent to extracting converged Ritz vectors from certain Krylov subspaces. As a special case, the single-shift qr algorithm enhanced with aggressive early deflation corresponds to a Krylov subspace method whose starting vector undergoes a Rayleigh-quotient iteration. It is shown how these observations can be used to derive improved convergence bounds for the qr algorithm.

关键词： qr algorithm deflation Krylov subspace convergence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：