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

作者： Garza-Vargas, Jorge University of California Berkeley

学位级别：Ph.D., Doctor of Philosophy

We rigorously analyze numerical methods for (approximately) computing the eigenvalues and eigenvectors of a matrix. Our main results are the following:• Spectral bisection. We show that a backward-stable solution to the eigenvalue problem can be obtained by a randomized algorithm in nearly matrix-multiplication time on any input. More specifically, we show that for every δ > 0, there is a randomized version of the spectral bisection algorithm that, on any input A ∈ C n×n , with probability 1 − O(1/n), finds matrices V, D ∈ C n×n with V invertible and D diagonal such that ∥A − V DV −1∥ ≤ δ∥A∥, using O(TMM(n)log2 (n/δ)) arithmetic operations, in finite arithmetic with O(log4 (n/δ)log n) bits of precision. Here TMM(n) is the number of arithmetic operations required to multiply two n × n complex matrices numerically stably, known to satisfy TMM(n) = O(n ω+η ) for every η > 0 where ω is the exponent of matrix multiplication.• The Hessenberg shifted qr algorithm. We introduce a randomized shifting strategy for the Hessenberg qr algorithm, for which we prove (in the finite precision arithmetic model) rapid global convergence. It follows from our results, that for any δ, ϕ > 0, a randomized version of the shifted Hessenberg qr algorithm can be used to compute, on any input A ∈ C n×n , with probability at least 1 − ϕ, matrices U, T ∈ C n×n with U unitary and T upper triangular, such that ∥A − UT U∗∥ ≤ δ∥A∥, using O(n3log(n/(δϕ))2 log log(n/(δϕ))) arithmetic operations performed using O(log2 (n/(δϕ))log log(n/(δϕ))) bits of precision. This provides the first rapidly globally convergent shifting strategy in the nonsymmetric case, which was an open problem even under the assumption of exact arithmetic.• The Lanczos algorithm. We analyze the Lanczos algorithm where the initial vector u is sampled uniformly at random from the unit sphere Sn−1 , and show that when run on a Hermitian input A ∈ Cn×n for c1 log n iterations (where c1 depends on some coarse global property of the spec

关键词： algorithmic analysis Diagonalization Lanczos algorithm qr algorithm Spectral bisection algorithm

来源：评论

学校读者我要写书评

暂无评论

The convergence of multi-shift qr algorithm for symmetric matrices

引用

APPLIED MATHEMATICS AND COMPUTATION 2013年 222卷 343-355页

作者： Su, Qifang Taizhou Univ Sch Math & Informat Engn Linhai 317000 Peoples R China

In this paper, we discuss the convergence of the double-shift and multi-shift qr algorithms for symmetric tridiagonal matrices. We analyze how to choose multi-shifts by comparing the relationships between the number of iterations, CPU time and the number of multi-shifts. Numerical tests and figures are performed. (C) 2013 Elsevier Inc. All rights reserved.

关键词： qr algorithm Eigenvalue Convergence Symmetric tridiagonal matrix Hessenberg matrix

来源：评论

学校读者我要写书评

暂无评论

Fast Principal Component Auto-Regressive algorithm for Estimation of Parameters of Radar Interference Signal 10

Fast Principal Component Auto-Regressive Algorithm for Estim...

引用

10th International Conference on Computing, Communication and Networking Technologies (ICCCNT)

作者： Hussain, Md. Shahnawaz Pal, Srikanta Birla Inst Technol ECE Dept Ranchi Bihar India

ISBN: (纸本)9781538659069

The issue of estimation of parameters of radar interference signal has been addressed by algorithms like Grid Search-Maximum Likelihood Estimator (GS-MLE) and Principal Component Auto-Regressive Estimator (PCAR). GS-MLE algorithm is an optimal algorithm as it achieves the Cramer-Rao Lower Bound (CRLB) but its time-complexity is high. Another algorithm, that is, the PCAR algorithm is a suboptimal algorithm but it is comparatively faster. In this paper, we propose a hybrid method to further reduce the time-complexity of the PCAR algorithm for large data size (>3000) at both high SNR (>0 dB) and low SNR (<0 dB). However, the estimates of parameters obtained by the Fast PCAR algorithm are reliable only in the SNR range of -20 dB to infinity. This is validated by comparing the Fast PCAR algorithm with the CRLB.

关键词： Principal Component AR algorithm Grid Search Maximum Likelihood Estimator CRLB qr algorithm Lanczos algorithm singular-value decomposition eigenvalues radar interference

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A GENERALIZATION OF THE MULTISHIFT qr algorithm

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2012年第3期33卷 759-779页

作者： 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 a generalization of Francis's implicitly shifted qr algorithm was proposed, notably widening the class of matrices admitting low-cost implicit qr steps. This unifying framework covered the methods and theory for Hessenberg and inverse Hessenberg matrices and furnished also new, single-shifted, qr-type methods for, e.g., CMV matrices. Convergence of this approach was only suggested by numerical experiments. No theoretical claims supporting the results were presented. In this paper we present multishift variants of these new algorithms. We also provide a convergence theory that shows that the new algorithm performs nested subspace iterations on rational Krylov subspaces. Numerical experiments confirm the validity of the theory.

关键词： CMV matrices eigenvalues qr algorithm rational Krylov subspace iteration

来源：评论

学校读者我要写书评

暂无评论

Comparison of V-BLAST/OSIC algorithm and the qr Decomposition algorithm

Comparison of V-BLAST/OSIC Algorithm and the QR Decompositio...

引用

2nd International Conference on Measurement, Information and Control (ICMIC)

作者： Zhang Xiuyan Zhang Min Zhao Qingfeng Pi Boyuan Liu Qingqiang Northeast Petr Univ Elect & Informat Engn Coll Daqing 163318 Peoples R China Daqing Oilfield Ltd Co Oil Prod Co 1 Daqing 163001 Peoples R China Daqing Oilfiled Daqing OilField Thermal Power Plant Daqing 163314 Peoples R China

ISBN: (纸本)9781479913909

MIMO-OFDM has become the core of future communication technologies for its great excellence, the detection algorithms are various, but only nonlinear algorithms are extensive used in practice. First, the ZF and MMSE criteria are briefly introduced, the nonlinear detection algorithms of V-BLAST algorithm and qr algorithm are analyzed in detail. Then the algorithms based on ZF criterion and MMSE criterion named ZF-OSIC, MMSE-OSIC, SqrD-ZF and SqrD-MMSE are studied. Finally the BER performance of them are compared, through MATLAB simulation.

关键词： V-BLAST algorithm qr algorithm MIMO-OFDM

来源：评论

学校读者我要写书评

暂无评论

Core-Chasing algorithms for the Eigenvalue Problem

引用

丛书名： Fundamentals of algorithms

2018年

作者： Jared L. Aurentz Thomas Mach Leonardo Robol Raf Vandebril David S. Watkins

ISBN: (数字)9781611975345

ISBN: (纸本)9781611975338

Eigenvalue computations are ubiquitous in science and engineering. John Francis's implicitly shifted qr algorithm has been the method of choice for small to medium sized eigenvalue problems since its invention in 1959. This book presents a new view of this classical algorithm. While Francis's original procedure chases bulges, the new version chases core transformations, which allows the development of fast algorithms for eigenvalue problems with a variety of special structures. This also leads to a fast and backward stable algorithm for computing the roots of a polynomial by solving the companion matrix eigenvalue problem. The authors received a SIAM Outstanding Paper prize for this work.

关键词： eigenvalue computation qr decomposition qr algorithm Francis algorithm backward stability

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Lightning Impulse Voltage Evaluation 6th

引用

6th Computer Science On-Line Conference (CSOC)

作者： Khodpun, Nopphadon Vilailak, Krisada Vongchavalitkul Univ Fac Engn Elect Engn Branch Nakhon Ratchasima Thailand

ISBN: (纸本)9783319572642

This research studied and developed software for lightning impulse voltage parameters evaluation. Full lightning impulse voltage of 9 cases in TDG program had been used as references for software tested. This software created 2 types of voltage waveform which are mean curve and approximate real curve. Kalman Filter had been used for mean curve. qr algorithm had been used for approximate real curve. The experimental results show that the purported software can evaluate all lightning impulse parameters as IEC 61083-2 standards in every case.

关键词： Lightning impulse voltage evaluation Kalman filter qr algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：