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

Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive lanczos Bisection

JOURNAL OF MACHINE LEARNING RESEARCH 2009年第9期10卷 1989-2012页

作者： Chen, Jie Fang, Haw-ren Saad, Yousef Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA Argonne Natl Lab Div Math & Comp Sci Argonne IL 60439 USA

Nearest neighbor graphs are widely used in data mining and machine learning. A brute-force method to compute the exact kNN graph takes Theta(dn(2)) time for n data points in the d dimensional Euclidean space. We propose two divide and conquer methods for computing an approximate kNN graph in Theta(dn(t)) time for high dimensional data (large d). The exponent t is an element of (1, 2) is an increasing function of an internal parameter a which governs the size of the common region in the divide step. Experiments show that a high quality graph can usually be obtained with small overlaps, that is, for small values of t. A few of the practical details of the algorithms are as follows. First, the divide step uses an inexpensive lanczos procedure to perform recursive spectral bisection. After each conquer step, an additional refinement step is performed to improve the accuracy of the graph. Finally, a hash table is used to avoid repeating distance calculations during the divide and conquer process. The combination of these techniques is shown to yield quite effective algorithms for building kNN graphs.

关键词： nearest neighbors graph high dimensional data divide and conquer lanczos algorithm spectral method

来源：评论

学校读者我要写书评

暂无评论

A CLASS OF lanczos-LIKE algorithmS IMPLEMENTED ON PARALLEL COMPUTERS

引用

PARALLEL COMPUTING 1991年第6-7期17卷 763-778页

作者： KIM, SK CHRONOPOULOS, AT Department of Computer Science University of Minnesota Minneapolis Minnesota 55455 USA

The lanczos algorithm is most commonly used in approximating a small number of extreme eigenvalues and eigenvectors for symmetric large sparse matrices. Main memory accesses for shared memory systems or global communications (synchronizations) in message passing systems decrease the computation speed. In this paper, the standard lanczos algorithm is restructured so that only one synchronization point is required;that is, one global communication in a message passing distributed-memory machine or one global memory sweep in a shared-memory machine per each iteration is required. We also introduce the s-step lanczos method for finding a few eigenvalues of symmetric large sparse matrices in a similar way to the s-step Conjugate Gradient method [2], and we prove that the s-step method generates reduction matrices which are similar to reduction matrices generated by the standard method. One iteration of the s-step lanczos algorithm corresponds to s iterations of the standard lanczos algorithm. The s-step method has improved data locality, minimized global communication and has superior parallel properties to the standard method. These algorithms are implemented on a 64-node NCUBE/seven hypercube and a CRAY-2, and performance results are presented.

关键词： lanczos algorithm EIGENVALUE PROBLEM SYMMETRICAL SPARSE MATRICES MULTIPROCESSOR SYSTEMS CRAY-2 NCUBE

来源：评论

学校读者我要写书评

暂无评论

A partial Pade-via-lanczos method for reduced-order modeling

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2001年第1期332卷 139-164页

作者： Bai, ZJ Freund, RW Bell Labs Lucent Technol Murray Hill NJ 07974 USA Univ Calif Davis Dept Comp Sci Davis CA 95616 USA

The classical lanczos process can be used to efficiently generate Fade approximants of the transfer function of a given single-input single-output time-invariant linear dynamical system. Unfortunately, in general, the resulting reduced-order models based on Pade approximation do not preserve the stability, and possibly passivity, of the original linear dynamical system. In this paper, we describe the use of partial Pade approximation for reduced-order modeling. Partial Pade approximants have a number of prescribed poles and zeros, while the remaining degrees of freedom are used to match the Taylor expansion of the original transfer function in as many leading coefficients as possible. We present an algorithm for computing partial Pade approximants via suitable rank-1 updates of the tridiagonal matrices generated by the lanczos process. Numerical results for two circuit examples are reported. (C) 2001 Elsevier Science Inc. All rights reserved.

关键词： lanczos algorithm linear dynamical system transfer function stability passivity partial Pade approximation VLSI circuit simulation

来源：评论

学校读者我要写书评

暂无评论

Using nonorthogonal lanczos vectors in the computation of matrix functions

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1998年第1期19卷 38-54页

作者： Druskin, V Greenbaum, A Knizhnerman, L Schlumberger Doll Res Ctr Ridgefield CT 06877 USA NYU Courant Inst Math Sci New York NY 10012 USA Cent Geophys Expedit Moscow 123298 Russia

The lanczos algorithm uses a three-term recurrence to construct an orthonormal basis for the Krylov space corresponding to a symmetric matrix A and a nonzero starting vector phi. The vectors and recurrence coefficients produced by this algorithm can be used for a number of purposes, including solving linear systems Au = phi and computing the matrix exponential e(-tA)phi. Although the vectors produced in finite precision arithmetic are not orthogonal, we show why they can still be used effectively for these purposes.

关键词： lanczos algorithm iterative methods matrix exponential finite precision arithmetic

来源：评论

学校读者我要写书评

暂无评论

Adaptive Rational Interpolation: Arnoldi and lanczos-like Equations

引用

EUROPEAN JOURNAL OF CONTROL 2008年第4期14卷 342-354页

作者： Frangos, Michalis Jaimoukha, Imad M. Univ London Imperial Coll Sci Technol & Med Dept Elect & Elect Engn London SW7 2AZ England

The Arnoldi and lanczos algorithms, which belong to the class of Krylov subspace methods, are increasingly used for model reduction of large-scale systems. The standard versions of the algorithms tend to create reduced order models that poorly approximate low frequency dynamics. Rational Arnoldi and lanczos algorithms produce reduced models that approximate dynamics at various frequencies. This paper tackles the issue of developing simple Arnoldi and lanczos equations,for the rational case. This allows a simple error analysis to be carried out for both algorithms and permits the development of computationally efficient model reduction algorithms, where the frequencies at which the dynamics are to be matched can be updated adaptively.

关键词： Model reduction Krylov subspaces Arnoldi algorithm lanczos algorithm rational interpolation adaptive interpolation

来源：评论

学校读者我要写书评

暂无评论

FAST ESTIMATION OF tr(f(A)) VIA STOCHASTIC lanczos QUADRATURE

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2017年第4期38卷 1075-1099页

作者： Ubaru, Shashanka Chen, Jie Saad, Yousef Univ Minnesota Comp Sci & Engn Minneapolis MN 55455 USA IBM Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

The problem of estimating the trace of matrix functions appears in applications ranging from machine learning and scientific computing, to computational biology. This paper presents an inexpensive method to estimate the trace of f (A) for cases where f is analytic inside a closed interval and A is a symmetric positive definite matrix. The method combines three key ingredients, namely, the stochastic trace estimator, Gaussian quadrature, and the lanczos algorithm. As examples, we consider the problems of estimating the log-determinant (f(t) = log(t)), the Schatten p-norms (f(t) = t(p/2)), the Estrada index (f(t) = e(t)), and the trace of the matrix inverse (f(t) = t(-1)). We establish multiplicative and additive error bounds for the approximations obtained by this method. In addition, we present error bounds for other useful tools such as approximating the log-likelihood function in the context of maximum likelihood estimation of Gaussian processes. Numerical experiments illustrate the performance of the proposed method on different problems arising from various applications.

关键词： trace estimation lanczos algorithm log-determinants fast approximate algorithms Schatten norms Gaussian processes

来源：评论

学校读者我要写书评

暂无评论

lanczos pseudospectral method for initial-value problems in electrodynamics and its applications to ionic crystal gratings

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2005年第2期209卷 643-664页

作者： Borisov, AG Shabanov, SV DIPC San Sebastian 20018 Spain Univ Paris 11 CNRS UMR 8625 Collis Atom & Mol Lab F-91405 Orsay France Univ Florida Dept Math Gainesville FL 32611 USA

Maxwell's equations are cast in the form of the Schrodinger equation. The lanczos propagation method is used in combination with the fast Fourier pseudospectral method to solve the initial-value problem. As a result, a time-domain, unconditionally stable, and highly efficient numerical algorithm is obtained for propagation and scattering of broadband electromagnetic pulses in dispersive and absorptive media. As compared to conventional finite-difference time-domain methods, an important advantage of the proposed algorithm is a dynamical control of accuracy: Variable time steps or variable computational costs per time step with error control are possible. The method is illustrated with numerical simulations of extraordinary transmission and reflection in metal, dielectric, and ionic crystal gratings with rectangular and cylindrical geometry. The effects of polaritonic excitations on transmission (reflection) properties of ionic crystal gratings in the infra-red range are investigated in detail. In particular, it is shown that, in addition to structural (geometric) resonances, resonant polaritonic excitations can drastically change light transmission. (c) 2005 Elsevier Inc. All rights reserved.

关键词： lanczos algorithm Arnoldi process Maxwell's equations time-domain algorithms pseudospectral methods gratings polaritonic excitations

来源：评论

学校读者我要写书评

暂无评论

A regularizing L-curve lanczos method for underdetermined linear systems

引用

APPLIED MATHEMATICS AND COMPUTATION 2001年第1期121卷 55-73页

作者： Morigi, S Sgallari, F Univ Bologna Dept Math CIRAM I-40127 Bologna Italy

Many real applications give rise to the solution of underdetermined linear systems of equations with a very ill conditioned matrix A, whose dimensions are so large as to make solution by direct methods impractical or infeasible. Image reconstruction from projections is a well-known example of such systems. In order to facilitate the computation of a meaningful approximate solution, we regularize the linear system, i.e., we replace it by a nearby system that is better conditioned. The amount of regularization is determined by a regularization parameter. Its optimal value is, in most applications, not known a priori. A well-known method to determine it is given by the L-curve approach, We present an iterative method based on the lanczos algorithm for inexpensively evaluating an approximation of the points on the L-curve and then determine the value of the optimal regularization parameter which lets us compute an approximate solution of the regularized system of equations. (C) 2001 Elsevier Science Inc. All rights reserved.

关键词： ill posed problems regularization L-curve criterion lanczos algorithm

来源：评论

学校读者我要写书评

暂无评论

lanczos Vectors versus Singular Vectors for Effective Dimension Reduction

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2009年第8期21卷 1091-1103页

作者： Chen, Jie Saad, Yousef Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA

This paper takes an in-depth look at a technique for computing filtered matrix-vector (mat-vec) products which are required in many data analysis applications. In these applications, the data matrix is multiplied by a vector and we wish to perform this product accurately in the space spanned by a few of the major singular vectors of the matrix. We examine the use of the lanczos algorithm for this purpose. The goal of the method is identical with that of the truncated singular value decomposition (SVD), namely to preserve the quality of the resulting mat-vec product in the major singular directions of the matrix. The lanczos-based approach achieves this goal by using a small number of lanczos vectors, but it does not explicitly compute singular values/vectors of the matrix. The main advantage of the lanczos-based technique is its low cost when compared with that of the truncated SVD. This advantage comes without sacrificing accuracy. The effectiveness of this approach is demonstrated on a few sample applications requiring dimension reduction, including information retrieval and face recognition. The proposed technique can be applied as a replacement to the truncated SVD technique whenever the problem can be formulated as a filtered mat-vec multiplication.

关键词： Dimension reduction SVD lanczos algorithm information retrieval latent semantic indexing face recognition PCA eigenfaces

来源：评论

学校读者我要写书评

暂无评论

NEWTON-TYPE MINIMIZATION VIA THE lanczos METHOD

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 1984年第4期21卷 770-788页

作者： NASH, SG

This paper discusses the use of the linear conjugate-gradient method (developed via the lanczos method) in the solution of large-scale unconstrained minimization problems. At each iteration of a Newton-type method, the direction of search is defined as the solution of a quadratic subproblem. When the number of variables is very large, this subproblem may be solved using the linear conjugate-gradient method of Hestenes and Stiefel. We show how the equivalent lanczos characterization of the linear conjugate-gradient method may be exploited to define a modified Newton method which can be applied to problems that do not necessarily have positive-definite Hessian matrices at all points of the region of interest. This derivation also makes it possible to compute a negative-curvature direction at a stationary point.

关键词： unconstrained optimization truncated-Newton algorithm modified matrix factorization lanczos algorithm linear conjugate-gradient algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：