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

Development of numerical linear algebra algorithms in dynamic fixed-point format: a case study of lanczos tridiagonalization

引用

INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS 2016年第6期44卷 1222-1262页

作者： Pradhan, Tapan Kabi, Bibek Mohanty, Ramanarayan Routray, Aurobinda Indian Inst Technol Dept Elect Engn Kharagpur 721302 W Bengal India Indian Inst Technol Adv Technol Dev Ctr Kharagpur 721302 W Bengal India

Proper range and precision analysis play an important role in the development of fixed-point algorithms for embedded system applications. Numerical linear algebra algorithms used to find singular value decomposition of symmetric matrices are suitable for signal and image-processing applications. These algorithms have not been attempted much in fixed-point arithmetic. The reason is wide dynamic range of data and vulnerability of the algorithms to round-off errors. For any real-time application, the range of the input matrix may change frequently. This poses difficulty for constant and variable fixed-point formats to decide on integer wordlengths during float-to-fixed conversion process because these formats involve determination of integer wordlengths before the compilation of the program. Thus, these formats may not guarantee to avoid overflow for all ranges of input matrices. To circumvent this problem, a novel dynamic fixed-point format has been proposed to compute integer wordlengths adaptively during runtime. lanczos algorithm with partial orthogonalization, which is a tridiagonalization step in computation of singular value decomposition of symmetric matrices, has been taken up as a case study. The fixed-point lanczos algorithm is tested for matrices with different dimensions and condition numbers along with image covariance matrix. The accuracy of fixed-point lanczos algorithm in three different formats has been compared on the basis of signal-to-quantization-noise-ratio, number of accurate fractional bits, orthogonality and factorization errors. Results show that dynamic fixed-point format either outperforms or performs on par with constant and variable formats. Determination of fractional wordlengths requires minimization of hardware cost subject to accuracy constraint. In this context, we propose an analytical framework for deriving mean-square-error or quantization noise power among lanczos vectors, which can serve as an accuracy constraint for wordlength

关键词： accuracy evaluation fixed-point arithmetic lanczos algorithm mean-square-error signal-to-quantization-noise-ratio singular value decomposition

来源：评论

学校读者我要写书评

暂无评论

A REFINED UNSYMMETRIC lanczos EIGENSOLVER FOR COMPUTING ACCURATE EIGENTRIPLETS OF A REAL UNSYMMETRIC MATRIX

引用

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2007年 28卷 95-113页

作者： Tremblay, Jean Christophe Carrington, Tucker, Jr. Univ Montreal Dept Chim Montreal PQ H3C 3J7 Canada

For most unsymmetric matrices it is difficult to compute many accurate eigenvalues using the primitive form of the unsymmetric lanczos algorithm (ULA). In this paper we propose a modification of the ULA. It is related to ideas used in [J. Chem. Phys. 122 (2005), 244107 (11 pages)] to compute resonance lifetimes. Using the refined ULA we suggest, the calculation of accurate extremal and interior eigenvalues is feasible. The refinement is simple: approximate right and left eigenvectors computed using the ULA are used to form a small projected matrix whose eigenvalues and eigenvectors are easily computed. There is no re-biorthogonalization of the lanczos vectors and no need to store large numbers of vectors in memory. The method can therefore be used to compute eigenvalues of very large matrices. The idea is tested on several matrices.

关键词： Eigenproblem unsymmetric matrices lanczos algorithm

来源：评论

学校读者我要写书评

暂无评论

On stabilization and convergence of clustered Ritz values in the lanczos method

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2005年第3期27卷 891-908页

作者： Wülling, W Univ Bielefeld Fak Math D-33501 Bielefeld Germany

The lanczos algorithm can be considered as an iterative method for finding a few eigenvalues and eigenvectors of large sparse symmetric matrices. In the present paper we solve a conjecture posed by Zdenek Strakos and Anne Greenbaum in [Open Questions in the Convergence Analysis of the lanczos Process for the Real Symmetric Eigenvalue Problem, IMA Research Report, 1992] on the clustering of Ritz values, which occurs in finite precision computations. In particular, we prove that the conjecture is valid in most cases and describe the rare case when it is not. The established upper bounds measuring the quality of Ritz approximations imply also that Ritz values cluster only close to an eigenvalue.

关键词： eigenvalues Ritz values lanczos algorithm tridiagonal matrix

来源：评论

学校读者我要写书评

暂无评论

Comparison of lanczos and CGS solvers for solving numerical heat transfer problems

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1999年第8期37卷 107-117页

作者： Sundar, S Bhagavan, BK Sastri, KS Indian Inst Technol Dept Math Kharagpur 721302 W Bengal India

In this paper, we have presented a comparative study of the lanczos solver with out preconditioning and Conjugate Gradient Squared (CGS) solver with preconditioning for solving numerical heat transfer problem. Our com... 详细信息

关键词： Krylov subspace lanczos algorithm preconditioning conjugate gradient squared algorithm nonsymmetric systems

来源：评论

学校读者我要写书评

暂无评论

Computation of large invariant subspaces using polynomial filtered lanczos iterations with applications in density functional theory

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2008年第1期30卷 397-418页

作者： Bekas, C. Kokiopoulou, E. Saad, Yousef Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA

The most expensive part of all electronic structure calculations based on density functional theory lies in the computation of an invariant subspace associated with some of the smallest eigenvalues of a discretized Hamiltonian operator. The dimension of this subspace typically depends on the total number of valence electrons in the system, and can easily reach hundreds or even thousands when large systems with many atoms are considered. At the same time, the discretization of Hamiltonians associated with large systems yields very large matrices, whether with planewave or real-space discretizations. The combination of these two factors results in one of the most significant bottlenecks in computational materials science. In this paper we show how to efficiently compute a large invariant subspace associated with the smallest eigenvalues of a symmetric/Hermitian matrix using polynomially filtered lanczos iterations. The proposed method does not try to extract individual eigenvalues and eigenvectors. Instead, it constructs an orthogonal basis of the invariant subspace by combining two main ingredients. The first is a filtering technique to dampen the undesirable contribution of the largest eigenvalues at each matrix-vector product in the lanczos algorithm. This technique employs a well-selected low pass filter polynomial, obtained via a conjugate residual-type algorithm in polynomial space. The second ingredient is the lanczos algorithm with partial reorthogonalization. Experiments are reported to illustrate the efficiency of the proposed scheme compared to state-of-the-art implicitly restarted techniques.

关键词： polynomial filtering conjugate residual lanczos algorithm density functional theory

来源：评论

学校读者我要写书评

暂无评论

A lanczos-type method for multiple starting vectors

引用

MATHEMATICS OF COMPUTATION 2000年第232期69卷 1577-1601页

作者： Aliaga, JI Boley, DL Freund, RW Hernández, V Univ Jaume 1 Dept Informat Castellon de La Plana 12071 Spain Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA Bell Labs Lucent Technol Murray Hill NJ 07974 USA Univ Politecn Valencia Dept Sistemas Informat & Computac E-46071 Valencia Spain

Given a square matrix and single right and left, starting vectors, the classical nonsymmetric lanczos process generates two sequences of biorthogonal basis vectors for the right and left Krylov subspaces induced by the given matrix and vectors. In this paper, we propose a lanczos-type algorithm that extends the classical lanczos process for single starting vectors to multiple starting vectors. Given a square matrix and two blocks of right and left starting vectors, the algorithm generates two sequences of biorthogonal basis vectors for the right and left block Krylov subspaces induced by the given data. The algorithm can handle the most general case of right and left starting blocks of arbitrary sizes, while all previously proposed extensions of the lanczos process are restricted to right and left starting blocks of identical sizes. Other features of our algorithm include a built-in deflation procedure to detect and delete linearly dependent vectors in the block Krylov sequences, and the option to employ look-ahead to remedy the potential breakdowns that may occur in nonsymmetric lanczos-type methods.

关键词： lanczos algorithm nonsymmetric matrix block Krylov subspaces biorthogonalization oblique projection deflation breakdown look-ahead

来源：评论

学校读者我要写书评

暂无评论

Explicit high-order time stepping based on componentwise application of asymptotic block lanczos iteration

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2012年第6期19卷 970-991页

作者： Lambers, James V. Univ So Mississippi Hattiesburg MS 39406 USA

This paper describes the development of explicit time stepping methods for linear PDEs that are specifically designed to cope with the stiffness of the system of ODEs that results from spatial discretization. As stiffness is caused by the contrasting behavior of coupled components of the solution, it is proposed to adopt a componentwise approach in which each coefficient of the solution in an appropriate basis is computed using an individualized approximation of the solution operator. This has been accomplished by Krylov subspace spectral (KSS) methods, which use techniques from matrices, moments and quadrature to approximate bilinear forms involving functions of matrices via block Gaussian quadrature rules. These forms correspond to coefficients with respect to the chosen basis of the application of the solution operator of the PDE to the solution at an earlier time. In this paper, it is proposed to substantially enhance the efficiency of KSS methods through the prescription of quadrature nodes on the basis of asymptotic analysis of the recursion coefficients produced by block lanczos iteration for each Fourier coefficient as a function of frequency. The potential of this idea is illustrated through numerical results obtained from the application of the modified KSS methods to diffusion equations and wave equations. Copyright (c) 2012 John Wiley & Sons, Ltd.

关键词： lanczos algorithm spectral methods Gaussian quadrature heat equation wave equation

来源：评论

学校读者我要写书评

暂无评论

The stabilization of weights in the lanczos and Conjugate Gradient method

引用

BIT NUMERICAL MATHEMATICS 2005年第2期45卷 395-414页

作者： Wülling, W Univ Bielefeld Fak Math D-33501 Bielefeld Germany

The lanczos and the Conjugate Gradient method both compute implicitly a sequence of Gauss quadrature approximations to a certain Riemann-Stieltjes integral. In finite precision computations the corresponding weight function will be slightly perturbed. The purpose of this paper is to solve a conjecture posed by Anne Greenbaum and Zdenek Strakos on the stabilization of weights for the Gauss quadrature approximations, i.e. in particular we prove that for a tight well separated cluster of Ritz values (nodes) an upper bound for the change in the sum of the corresponding weights can be developed that depends mainly on the ratio of the cluster diameter and the gap in the spectrum.

关键词： lanczos algorithm Conjugate Gradient method tridiagonal matrix Gauss-quadrature stabilization of weights

来源：评论

学校读者我要写书评

暂无评论

Transpose-free formulations of lanczos-type methods for nonsymmetric linear systems

引用

NUMERICAL algorithmS 1998年第1-2期17卷 51-66页

作者： Chan, TF de Pillis, L van der Vorst, H Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA Harvey Mudd Coll Dept Math Claremont CA 91711 USA Univ Utrecht Inst Math NL-3508 TA Utrecht Netherlands

We present a transpose-free version of the nonsymmetric scaled lanczos procedure. It generates the same tridiagonal matrix as the classical algorithm, using two matrix-vector products per iteration without accessing A(T). We apply this algorithm to obtain a transpose-free version of the Quasi-minimal residual method of Freund and Nachtigal [15] (without look-ahead), which requires three matrix-vector products per iteration. We also present a related transpose-free version of the bi-conjugate gradients algorithm.

关键词： lanczos algorithm quasi-minimal residual algorithm bi-conjugate gradients algorithm nonsymmetric linear systems Krylov subspace methods

来源：评论

学校读者我要写书评

暂无评论

lanczos-type algorithms with embedded interpolation and extrapolation models for solving large-scale systems of linear equations

引用

INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND MATHEMATICS 2019年第5期10卷 429-442页

作者： Maharani, Maharani Larasati, Niken Salhi, Abdellah Khan, Wali Mashwani Univ Jenderal Soedirman Dept Math Purwokerto Jawa Tengah Indonesia Univ Essex Dept Math Sci Wivenhoe Pk Colchester CO4 3YS Essex England Univ Sci & Technol Dept Math Kohat Pakistan

The new approach to combating instability in lanczos-type algorithms for large-scale problems is proposed. It is a modification of so called the embedded interpolation and extrapolation model in lanczos-type algorithms (EIEMLA), which enables us to interpolate the sequence of vector solutions generated by a lanczos-type algorithm entirely, without rearranging the position of the entries of the vector solutions. The numerical results show that the new approach performs more effectively than the EIEMLA. In fact, we extend this new approach on the use of a restarting framework to obtain the convergence of lanczos algorithms accurately. This kind of restarting challenges other existing restarting strategies in lanczos-type algorithms.

关键词： lanczos algorithm interpolation extrapolation systems of linear equations embedded interpolation and extrapolation model in lanczos-type algorithms EIEMLA restarting strategy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：