Accurate eigenvalues of certain sign regular matrices

被引:21
作者
Koev, Plamen
Dopico, Froilan
机构
[1] MIT, Dept Math, Cambridge, MA 02139 USA
[2] Univ Madrid 3, Dept Matemat, Leganes 28911, Spain
基金
美国国家科学基金会;
关键词
eigenvalues; high relative accuracy; sign regular matrices; totally nonnegative matrices;
D O I
10.1016/j.laa.2007.02.012
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We present a new O(n(3)) algorithm for computing all eigenvalues of certain sign regular matrices to high relative accuracy in floating point arithmetic. The accuracy and cost are unaffected by the conventional eigenvalue condition numbers. A matrix is called sign regular when the signs of its nonzero minors depend only of the order of the minors. The sign regular matrices we consider are the ones which are nonsingular and whose kth order nonzero minors are of sign (-1)(k(k-1)/2) for all k. This class of matrices can also be characterized as nonsingular totally nonnegative matrices with columns in reverse order". We exploit a characterization of these particular sign regular matrices as products of nonnegative bidiagonals and the reverse identity. We arrange the computations in such a way that no subtractive cancellation is encountered, thus guaranteeing high relative forward accuracy. (c) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码:435 / 447
页数:13
相关论文
共 18 条
[1]  
Alfa AS, 2002, NUMER MATH, V90, P401, DOI [10.1007/s002110100289, 10.1007/S002110100289]
[2]  
ANDERSON E, 1999, LAPACK USERS GUIDE S, V9
[3]   The accurate and efficient solution of a totally positive generalized Vandermonde linear system [J].
Demmel, J ;
Koev, P .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2005, 27 (01) :142-152
[4]   Computing the singular value decomposition with high relative accuracy [J].
Demmel, J ;
Gu, M ;
Eisenstat, S ;
Slapnicar, I ;
Veselic, K ;
Drmac, Z .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1999, 299 (1-3) :21-80
[5]   Accurate SVDs of weakly diagonally dominant M-matrices [J].
Demmel, J ;
Koev, P .
NUMERISCHE MATHEMATIK, 2004, 98 (01) :99-104
[6]   ACCURATE SINGULAR-VALUES OF BIDIAGONAL MATRICES [J].
DEMMEL, J ;
KAHAN, W .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1990, 11 (05) :873-912
[7]   Accurate singular value decompositions of structured matrices [J].
Demmel, J .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2000, 21 (02) :562-580
[8]   Accurate symmetric rank revealing and eigendecompositions of symmetric structured matrices [J].
Dopico, Froilan M. ;
Koev, Plamen .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2006, 28 (04) :1126-1156
[9]   ON ACCURATE COMPUTATIONS OF THE PERRON ROOT [J].
ELSNER, L ;
KOLTRACHT, I ;
NEUMANN, M ;
XIAO, D .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1993, 14 (02) :456-467
[10]  
Gantmacher FR, 2002, OSCILLATION MATRICES