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

Fixed-precision randomized low-rank approximation methods for nonlinear model order reduction of large systems

INTERNATIONAL JOURNAL FOR numerical METHODS IN ENGINEERING 2019年第8期119卷 687-711页

作者： Bach, C. Duddeck, F. Song, L. Tech Univ Munich Dept Civil Geo & Environm Engn Munich Germany Res & Innovat Ctr BMW Grp Munich Germany Queen Mary Univ London Sch Engn & Mat Sci London England

Many model order reduction (MOR) methods employ a reduced basis V is an element of Rmxk to approximate the state variables. For nonlinear models, V is often computed using the snapshot method. The associated low-rank approximation of the snapshot matrix A is an element of Rmxn can become very costly as m,n grow larger. Widely used conventional singular value decomposition methods have an asymptotic time complexity of O(min(mn2,m2n)), which often makes them impractical for the reduction of large models with many snapshots. Different methods have been suggested to mitigate this problem, including iterative and incremental approaches. More recently, the use of fast and accurate randomized methods was proposed. However, most work so far has focused on fixed-rank approximations, where rank k is assumed to be known a priori. In case of nonlinear MOR, stating a bound on the precision is usually more appropriate. We extend existing research on randomized fixed-precision algorithms and propose a new heuristic for accelerating reduced basis computation by predicting the rank. Theoretical analysis and numerical results show a good performance of the new algorithms, which can be used for computing a reduced basis from large snapshot matrices, up to a given precision epsilon.

关键词： nonlinear dynamics nonlinear model order reduction randomized numerical linear algebra randomized SVD rank-revealing methods

来源：评论

学校读者我要写书评

暂无评论

SKETCHING FOR PRINCIPAL COMPONENT REGRESSION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2019年第2期40卷 454-485页

作者： Mor-Yosef, Liron Avron, Haim Tel Aviv Univ Sch Math Sci IL-6997801 Tel Aviv Israel

Principal component regression (PCR) is a useful method for regularizing least squares approximations. Although conceptually simple, straightforward implementations of PCR have high computational costs and so are inappropriate for large scale problems. In this paper, we propose efficient algorithms for computing approximate PCR solutions that, on one hand, are high quality approximations to the true PCR solutions (when viewed as minimizer of a constrained optimization problem) and, on the other hand, entertain rigorous risk bounds (when viewed as statistical estimators). In particular, we propose an input sparsity time algorithms for approximate PCR. We also consider computing an approximate PCR in the streaming model and kernel PCR. Empirical results demonstrate the excellent performance of our proposed methods.

关键词： sketching randomized numerical linear algebra linear regression least squares principal component regression compressed least squares

来源：评论

学校读者我要写书评

暂无评论

randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems

引用

INTERNATIONAL JOURNAL FOR numerical METHODS IN ENGINEERING 2019年第4期118卷 209-241页

作者： Bach, C. Ceglia, D. Song, L. Duddeck, F. Tech Univ Munich Dept Civil Geo & Environm Engn Munich Germany BMW Grp Res & Innovat Ctr Munich Germany Politecn Torino Dept Mech & Aerosp Engn Turin Italy Queen Mary Univ London Sch Engn & Mat Sci London England

Projection-based nonlinear model order reduction (MOR) methods typically make use of a reduced basis V is an element of R-mxk to approximate high-dimensional quantities. However, the most popular methods for computing V, eg, through a singular value decomposition of an m x n snapshot matrix, have asymptotic time complexities of (O(min(mn(2), m(2)n)) and do not scale well as m and n increase. This is problematic for large dynamical problems with many snapshots, eg, in case of explicit integration. In this work, we propose the use of randomized methods for reduced basis computation and nonlinear MOR, which have an asymptotic complexity of only (O(mnk) or (9(mn log(k)). We evaluate the suitability of randomized algorithms for nonlinear MOR and compare them to other strategies that have been proposed to mitigate the demanding computing times incurred by large nonlinear models. We analyze the computational complexities of traditional, iterative, incremental, and randomized algorithms and compare the computing times and accuracies for numerical examples. The results indicate that randomized methods exhibit an extremely high level of accuracy in practice, while generally being faster than any other analyzed approach. We conclude that randomized methods are highly suitable for the reduction of large nonlinear problems.

关键词： explicit FEM low-rank approximation nonlinear dynamics nonlinear model order reduction randomized numerical linear algebra randomized SVD

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms of maximum likelihood estimation with spatial autoregressive models for large-scale networks

引用

STATISTICS AND COMPUTING 2019年第5期29卷 1165-1179页

作者： Li, Miaoqi Kang, Emily L. Univ Cincinnati Dept Math Sci Cincinnati OH 45221 USA

The spatial autoregressive (SAR) model is a classical model in spatial econometrics and has become an important tool in network analysis. However, with large-scale networks, existing methods of likelihood-based inference for the SAR model become computationally infeasible. We here investigate maximum likelihood estimation for the SAR model with partially observed responses from large-scale networks. By taking advantage of recent developments in randomized numerical linear algebra, we derive efficient algorithms to estimate the spatial autocorrelation parameter in the SAR model. Compelling experimental results from extensive simulation and real data examples demonstrate empirically that the estimator obtained by our method, called the randomized maximum likelihood estimator, outperforms the state of the art by giving smaller bias and standard error, especially for large-scale problems with moderate spatial autocorrelation. The theoretical properties of the estimator are explored, and consistency results are established.

关键词： Maximum likelihood estimation Network randomized numerical linear algebra Spatial autoregressive model

来源：评论

学校读者我要写书评

暂无评论

Approximations of Schatten Norms via Taylor Expansions 1

引用

14th International Computer Science Symposium in Russia (CSR)

作者： Braverman, Vladimir Johns Hopkins Univ Baltimore MD 21218 USA

ISBN: (数字)9783030199555

ISBN: (纸本)9783030199555;9783030199548

In many applications of data science and machine learning data is represented by large matrices. Fast and accurate analysis of such matrices is a challenging task that is of paramount importance for the aforementioned applications. randomized numerical linear algebra (RNLA) is an popular area of research that often provides such fast and accurate algorithmic methods for massive matrix computations. Many critical problems in RNLA boil down to approximating spectral functions and one of the most fundamental examples of such spectral functions is Schatten p norm. The p-th Schatten norm for matrix A is an element of R-n1xn2 is defined as the l(p) norm of a vector comprised of singular values of matrix A, i.e., parallel to A parallel to(p) = ((i=1)Sigma(min(n1,n2)) vertical bar sigma i(A)vertical bar(p))(1/p), where sigma(i) (A) is the i-th singular value of A. In this paper we consider symmetric, positive semidefinite (SPSD) matrix A and present an algorithm for computing the p-Schatten norm AMP. Our methods are simple and easy to implement and can be extended to general matrices. Our algorithms improve, for a range of parameters, recent results of Musco, Netrapalli, Sidford, Ubaru and Woodruff (ITCS 2018), e.g., for p > 2 and sufficiently small values of epsilon.

关键词： randomized numerical linear algebra Schatten norms Algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast, Sparse Matrix Factorization and Matrix algebra via Random Sampling for Integral Equation Formulations in Electromagnetics

Fast, Sparse Matrix Factorization and Matrix Algebra via Ran...

引用

作者： Owen Tanner Wilkerson University of Kentucky

学位级别：硕士

Many systems designed by electrical & computer engineers rely on electromagnetic (EM) signals to transmit, receive, and extract either information or energy. In many cases, these systems are large and complex. Their accurate, cost-effective design requires high-fidelity computer modeling of the underlying EM field/material inter- action problem in order to find a design with acceptable system performance. This modeling is accomplished by projecting the governing Maxwell equations onto fi- nite dimensional subspaces, which results in a large matrix equation representation (Zx = b) of the EM problem. In the case of integral equation-based formulations of EM problems, the M-by-N system matrix, Z, is generally dense. For this reason, when treating large problems, it is necessary to use compression methods to store and manipulate Z. One such sparse representation is provided by so-called H 2 ma- trices. At low-to-moderate frequencies, H 2 matrices provide a controllably accurate data-sparse representation of Z. The scale at which problems in EM are considered "large" is continuously being redefined to be larger. This growth of problem scale is not only happening in EM, but respectively across all other sub-fields of computational science as well. The pursuit of increasingly large problems is unwavering in all these sub-fields, and this drive has long outpaced the rate of advancements in processing and storage capabilities in computing. This has caused computational science communities to now face the computational limitations of standard linear algebraic methods that have been relied upon for decades to run quickly and efficiently on modern computing hardware. This common set of algorithms can only produce reliable results quickly and efficiently for small to mid-sized matrices that fit into the memory of the host computer. There- fore, the drive to pursue larger problems has even began to outpace the reasonable capabilities of these common numerical algorithms; the dete

关键词： numerical simulations randomized numerical linear algebra computational electromagnetics computational linear algebra

来源：评论

学校读者我要写书评

暂无评论

A randomized least squares solver for terabyte-sized dense overdetermined systems

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2019年 36卷

作者： Iyer, Chander Avron, Haim Kollias, Georgios Ineichen, Yves Carothers, Christopher Drineas, Petros Rensselaer Polytech Inst Dept Comp Sci 110 8th St Troy NY 12180 USA Tel Aviv Univ Dept Appl Math POB 39040 Tel Aviv Israel IBM Res TJ Watson Res Ctr Yorktown Hts NY USA IBM Res Zurich Res Lab Zurich Switzerland

We present a fast randomized least-squares solver for distributed-memory platforms. Our solver is based on the Blendenpik algorithm, but employs multiple random projection schemes to construct a sketch of the input matrix. These random projection sketching schemes, and in particular the use of the randomized Discrete Cosine Transform, enable our algorithm to scale the distributed memory vanilla implementation of Blendenpik to terabyte-sized matrices and provide up to x7.5 speedup over a state-of-the-art scalable least-squares solver based on the classic QR algorithm. Experimental evaluations on terabyte scale matrices demonstrate excellent speedups on up to 16,384 cores on a Blue Gene/Q supercomputer. (C) 2016 Elsevier B.V. All rights reserved.

关键词： randomized numerical linear algebra High-performance computing Dense least squares regression

来源：评论

学校读者我要写书评

暂无评论

Detecting localized eigenstates of linear operators

引用

RESEARCH IN THE MATHEMATICAL SCIENCES 2018年第3期5卷 1-14页

作者： Lu, Jianfeng Steinerberger, Stefan Duke Univ Dept Math Box 90320 Durham NC 27708 USA Duke Univ Dept Phys Box 90320 Durham NC 27708 USA Duke Univ Dept Chem Box 90320 Durham NC 27708 USA Yale Univ Dept Math New Haven CT 06511 USA

We describe a way of detecting the location of localized eigenvectors of the eigenvalue problem Ax = lambda x for eigenvalues lambda with vertical bar lambda vertical bar comparatively large. We define the family of functions f(alpha) : {1, 2,..., n} -> R f(alpha)(k) = log (parallel to A(alpha)e(k)parallel to(l2)), where alpha >= 0 is a parameter and e(k) = (0, 0,..., 0, 1, 0,..., 0) is the kth standard basis vector. We prove that eigenvectors associated with eigenvalues with large absolute value localize around local maxima of f(alpha): the metastable states in the power iteration method (slowing down its convergence) can be used to predict localization. We present a fast randomized algorithm and discuss different examples: a random band matrix, discretizations of the local operator -Delta + V, and the nonlocal operator (-Delta)(3/4) + V.

关键词： Eigenvectors Localization Power iteration randomized numerical linear algebra Anderson localization

来源：评论

学校读者我要写书评

暂无评论

Spectral condition-number estimation of large sparse matrices

引用

numerical linear algebra WITH APPLICATIONS 2019年第3期26卷

作者： Avron, Haim Druinsky, Alex Toledo, Sivan Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Comp Sci Tel Aviv Israel

We describe a randomized Krylov-subspace method for estimating the spectral condition number of a real matrix A or indicating that it is numerically rank deficient. The main difficulty in estimating the condition number is the estimation of the smallest singular value sigma min of A. Our method estimates this value by solving a consistent linear least squares problem with a known solution using a specific Krylov-subspace method called LSQR. In this method, the forward error tends to concentrate in the direction of a right singular vector corresponding to sigma min. Extensive experiments show that the method is able to estimate well the condition number of a wide array of matrices. It can sometimes estimate the condition number when running dense singular value decomposition would be impractical due to the computational cost or the memory requirements. The method uses very little memory (it inherits this property from LSQR), and it works equally well on square and rectangular matrices.

关键词： condition-number estimation Krylov methods randomized numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

Universality laws for randomized dimension reduction, with applications

引用

INFORMATION AND INFERENCE-A JOURNAL OF THE IMA 2018年第3期7卷 337-446页

作者： Oymak, Samet Tropp, Joel A. Simons Inst Theory Comp Melvin Calvin Lab Berkeley CA 94720 USA CALTECH Comp & Math Sci 1200 E Calif BlvdMC 305-16 Pasadena CA 91125 USA

Dimension reduction is the process of embedding high-dimensional data into a lower dimensional space to facilitate its analysis. In the Euclidean setting, one fundamental technique for dimension reduction is to apply a random linear map to the data. This dimension reduction procedure succeeds when it preserves certain geometric features of the set. The question is how large the embedding dimension must be to ensure that randomized dimension reduction succeeds with high probability. This article studies a natural family of randomized dimension reduction maps and a large class of data sets. It proves that there is a phase transition in the success probability of the dimension reduction map as the embedding dimension increases. For a given data set, the location of the phase transition is the same for all maps in this family. Furthermore, each map has the same stability properties, as quantified through the minimum RSV. These results can be viewed as new universality laws in high-dimensional stochastic geometry. Universality laws for randomized dimension reduction have many applications in applied mathematics, signal processing and statistics. They yield design principles for numerical linear algebra algorithms, for compressed sensing measurement ensembles and for random linear codes. Furthermore, these results have implications for the performance of statistical estimation methods under a large class of random experimental designs.

关键词： conic geometry convex geometry dimension reduction invariance principle limit theorem random code random matrix randomized numerical linear algebra signal reconstruction statistical estimation stochastic geometry universality

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：