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

qr algorithm with two-sided Rayleigh quotient shifts

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2023年第5期30卷 e2487-e2487页

作者： Chen, Xiao Shan Xu, Hongguo South China Normal Univ Sch Math Guangzhou Guangdong Peoples R China Univ Kansas Dept Math Lawrence KS USA Univ Kansas Dept Math Lawrence KS 66045 USA

We introduce the two-sided Rayleigh quotient shift to the qr algorithm for non-Hermitian matrices to achieve a cubic local convergence rate. For the singly shifted case, the two-sided Rayleigh quotient iteration is incorporated into the qr iteration. A modified version of the method and its truncated version are developed to improve the efficiency. Based on the observation that the Francis double-shift qr iteration is related to a 2D Grassmann-Rayleigh quotient iteration, A doubly shifted qr algorithm with the two-sided 2D Grassmann-Rayleigh quotient double-shift is proposed. A modified version of the method and its truncated version are also developed. Numerical examples are presented to show the convergence behavior of the proposed algorithms. Numerical examples also show that the truncated versions of the modified methods outperform their counterparts including the standard Rayleigh quotient single-shift and the Francis double-shift.

关键词： local convergence rate qr algorithm qr iteration two-sided 2D Grassmann-Rayleigh quotient double-shift two-sided Rayleigh quotient shift

来源：评论

学校读者我要写书评

暂无评论

algorithm 1019: A Task-based Multi-shift qr/QZ algorithm with Aggressive Early Deflation

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2022年第1期48卷 11-11页

作者： Myllykoski, Mirko Umea Univ Dept Comp Sci SE-90187 Umea Sweden Umea Univ HPC2N SE-90187 Umea Sweden

The qr algorithm is one of the three phases in the process of computing the eigenvalues and the eigenvectors of a dense nonsymmetric matrix. This paper describes a task-based qr algorithm for reducing an upper Hessenberg matrix to real Schur form. The task-based algorithm also supports generalized eigenvalue problems (QZ algorithm) but this paper concentrates on the standard case. The task-based algorithm adopts previous algorithmic improvements, such as tightly-coupled multi-shifts and Aggressive Early Deflation (AED), and also incorporates several new ideas that significantly improve the performance. This includes, but is not limited to, the elimination of several synchronization points, the dynamic merging of previously separate computational steps, the shortening and the prioritization of the critical path, and experimental GPU support. The task-based implementation is demonstrated to be multiple times faster than multi-threaded LAPACK and ScaLAPACK in both single-node and multi-node configurations on two different machines based on Intel and AMD CPUs. The implementation is built on top of the StarPU runtime system and is part of the open-source StarNEig library.

关键词： Eigenvalue problem real Schur form qr algorithm QZ algorithm multi-shift aggressive early deflation task-based StarPU shared memory distributed memory MPI GPU

来源：评论

学校读者我要写书评

暂无评论

An extended Hamiltonian qr algorithm

引用

CALCOLO 2017年第3期54卷 1097-1120页

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

An extended qr algorithm specifically tailored for Hamiltonian matrices is presented. The algorithm generalizes the customary Hamiltonian qr algorithm with additional freedom in choosing between various possible extended Hamiltonian Hessenberg forms. We introduced in Ferranti et al. (Calcolo, 2015. doi10.1007/s10092-016-0192-1) an algorithm to transform certain Hamiltonian matrices to such forms. Whereas the convergence of the classical qr algorithm is related to classical Krylov subspaces, convergence in the extended case links to extended Krylov subspaces, resulting in a greater flexibility, and possible enhanced convergence behavior. Details on the implementation, covering the bidirectional chasing and the bulge exchange based on rotations are presented. The numerical experiments reveal that the convergence depends on the selected extended forms and illustrate the validity of the approach.

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

来源：评论

学校读者我要写书评

暂无评论

A note on the convergence theorem of the tridiagonal qr algorithm with Wilkinson's shift

引用

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS 2015年第2期32卷 465-487页

作者： Aishima, Kensuke Univ Tokyo Bunkyo Ku Tokyo 113 Japan

We discuss the convergence rate of the qr algorithm with Wilkinson's shift for tridiagonal symmetric eigenvalue problems. It is well known that the convergence rate is theoretically at least quadratic, and practically better than cubic for most matrices. In an effort to derive the convergence rate, the limiting patterns of some lower right submatrices have been intensively investigated. In this paper, we first describe a new limiting pattern of the lower right 3-by-3 submatrix with a concrete example, and then prove that the convergence rate of this new pattern is strictly cubic. In addition, we stress that our analysis identifies three classes of the limiting patterns of the tridiagonal qr algorithm with Wilkinson's shift.

关键词： Numerical linear algebra Eigensolver qr algorithm Symmetric tridiagonal matrices Wilkinson's shift Convergence rate

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Asymmetric healthcare biometric image encryption and watermarking technique using QZ synthesis and qrD algorithm

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2024年第31期83卷 76223-76245页

作者： Khurana, Mehak Rakheja, Pankaj NorthCap Univ Dept CSE Gurugram 122017 India

The research paper introduces an advanced asymmetric biometric image encryption technique that integrates Quasi-Zernike synthesis (QZS), qr algorithm, and hybrid transforms for enhanced security and integrity. The encryption process incorporates qr decomposition, generating an orthogonal matrix Q that adds obfuscation and randomness to the image representation. qr is also resilient to attacks that exploit vulnerabilities in PTFT-based cryptosystems. QZS further improves security by capturing spatial information and complex features. The use of the compressed sparse row (CSR) format enables efficient storage and secure transmission. This integration provides a robust solution for confidential, secure image communication, applicable in military, surveillance, and sensitive data transfer scenarios. Moreover, watermarking ensures protection from unauthorized access, strengthening security measures. Experimental evaluations demonstrate the proposed algorithm's robustness against common attacks, including noise addition, compression, and filtering. The results showcase high-quality image reconstruction, negligible information loss, affirming the scheme's effectiveness in achieving secure image encryption.

关键词： Asymmetric Encryption Quasi-Zernike Synthesis (QZS) qr algorithm Hybrid Transforms Watermarking

来源：评论

学校读者我要写书评

暂无评论

High-Performance of Eigenvalue Decomposition on FPGA for the DOA Estimation

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2023年第5期72卷 5782-5797页

作者： Zhang, Xiao-Wei Yan, Di Zuo, Lei Li, Ming Guo, Jian-Xin Xidian Univ Natl Lab Radar Signal Proc Xian 710126 Peoples R China Xijing Univ Sch Informat Engn Xian 710123 Peoples R China Changan Univ Sch Informat Engn Xian 710064 Peoples R China

For the direction of arrival (DOA) in array signal processing, eigenvalue decomposition (EVD) is one key issue in hardware implementation of the multiple signal classification (MUSIC) algorithm. Therefore, we introduce the look-ahead simplified one-sided Jacobi's method to efficiently decompose those symmetric matrices in this article and prove that the new method has the best orthogonality of eigenvector and locates eigenvectors closest to the true solution in theory. Both the numerical performance and real-time are important in engineering, so we present the novel flexible hardware architecture in single floating point arithmetic for EVD on field-programmable gate arrays (FPGAs). Finally, the simulated and raw data are used to investigate the performance of some different approaches in the context of both the EVD and MUSIC algorithm. The experimental results show that our proposed method has the best performance.

关键词： Matrix decomposition Jacobian matrices Field programmable gate arrays Eigenvalues and eigenfunctions Hardware Signal processing algorithms Multiple signal classification Eigenvalue decomposition (EVD) field-programmable gate array (FPGA) MUSIC Jacobi's method matrix inversion partial sorter qr algorithm

来源：评论

学校读者我要写书评

暂无评论

Pole-Swapping algorithms for the Eigenvalue Problem

引用

丛书名： SIAM Spotlights

2025年

作者： Daan Camps Thomas Mach Raf Vandebril David S. Watkins

Get 10% off by pre-ordering this book.This item has not yet published. Pre-order now and we will ship and process payment when the book becomes available.To pre-order contact Customer Service:800-447-SIAM (US &amp... 详细信息

ISBN: (数字)9781611978377

ISBN: (纸本)9781611978360

Get 10% off by pre-ordering this book.

This item has not yet published. Pre-order now and we will ship and process payment when the book becomes available.

To pre-order contact Customer Service:

800-447-SIAM (US & Canada)

215-382-9800 (outside US & Canada)

siambooks@***

Do not send credit card details via email.

Prices: List $48.60 / Member $34.02

Publishing May 2025

Matrix eigenvalue problems arise in a wide variety of fields in science and engineering, so it is important to have reliable and efficient methods for solving them. Of the methods devised, bulge-chasing algorithms, such as the famous qr and QZ algorithms, are the most important. This book focuses on pole-swapping algorithms, a new class of methods that are generalizations of bulge-chasing algorithms and a bit faster and more accurate owing to their inherent flexibility. The pole-swapping theory developed by the authors sheds light on the functioning of the whole class of algorithms, including qr and QZ.

Pole-Swapping algorithms for the Eigenvalue Problem

is the only book on the topic,
describes the state of the art on eigenvalue methods, and
provides an improved understanding and explanation of why these important algorithms work.

关键词： Eigenvalue problems QZ algorithm qr algorithm bulge chasing pole swapping core transformations

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：