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

International Conference for High Performance Computing, Networking, Storage and Analysis (HPC)

作者： Cheshmi, Kazem Cetinic, Zachary Dehnavi, Maryam Mehri Univ Toronto Toronto ON Canada

ISBN: (纸本)9781665454445

The compact data structures and irregular computation patterns in sparse matrix computations introduce challenges to vectorizing these codes. Available approaches primarily vectorize strided computation regions of a sparse code. In this work, we propose a locality-based codelet mining (LCM) algorithm that efficiently searches for strided and partially strided regions in sparse matrix computations for vectorization. We also present a classification of partially strided codelets and a differentiation-based approach to generate codelets from memory accesses in the sparse computation. LCM is implemented as an inspector-executor framework called LCM I/E that generates vectorized code for the sparse matrix-vector multiplication (SpMV), sparse matrix times dense matrix (SpMM), and sparse triangular solver (SpTRSV). LCM I/E outperforms the MKL library with an average speedup of 1.67x, 4.1x, and 1.75x for SpMV, SpTRSV, and SpMM, respectively. It is also faster than the state-of-the-art inspector-executor framework Sympiler [1] for the SpTRSV kernel with an average speedup of 1.9x.

关键词： Vectorization Parallel programming Polyhedral analysis sparse matrix computation

来源：评论

学校读者我要写书评

暂无评论

The hierarchical-likelihood approach to autoregressive stochastic volatility models

引用

computationAL STATISTICS & DATA ANALYSIS 2011年第1期55卷 248-260页

作者： Lee, Woojoo Lim, Johan Lee, Youngjo del Castillo, Joan Seoul Natl Univ Dept Stat Seoul 151747 South Korea Univ Autonoma Barcelona Barcelona 08192 Spain

Many volatility models used in financial research belong to a class of hierarchical generalized linear models with random effects in the dispersion. Therefore, the hierarchical-likelihood (h-likelihood) approach can be used. However, the dimension of the Hessian matrix is often large, so techniques of sparse matrix computation are useful to speed up the procedure of computing the inverse matrix. Using numerical studies we show that the h-likelihood approach gives better long-term prediction for volatility than the existing MCMC method, while the MCMC method gives better short-term prediction. We show that the h-likelihood approach gives comparable estimations of fixed parameters to those of existing methods. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Autoregressive stochastic volatility model Hierarchical generalized linear model Hierarchical likelihood sparse matrix computation Prediction

来源：评论

学校读者我要写书评

暂无评论

PARALLEL HYBRID PRECONDITIONING: INCOMPLETE FACTORIZATION WITH SELECTIVE sparse APPROXIMATE INVERSION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2010年第3期32卷 1323-1345页

作者： Raghavan, Padma Teranishi, Keita Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA

We consider parallel preconditioning to solve large sparse linear systems Ax = b using conjugate gradients when A is symmetric and positive definite. We develop a preconditioner that can be viewed as a hybrid of incomplete factorization and sparse approximate inversion schemes. Such a hybrid can potentially enable fast and reliable solution through a preconditioner with low memory requirements that allows latency-tolerant construction and application on multiprocessor systems. We propose a parallel hybrid scheme which yields a preconditioner as a tree-structured aggregate of sparse incomplete factors and inverses of selected submatrices. We analyze the computation and communication costs of our hybrid preconditioner and report on its parallel performance on some well-known test matrices. Our results indicate that our hybrid has significant advantages over sparse approximate inverse preconditioners and incomplete Cholesky preconditioners using either drop-threshold or zero-level-of-fill schemes.

关键词： sparse matrix computation numerical linear algebra parallel computing preconditioning

来源：评论

学校读者我要写书评

暂无评论

An efficient architecture for motion estimation and compensation in the transform domain

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2006年第2期16卷 191-201页

作者： Lee, J Vijaykrishnan, N Irwin, MJ Wolf, W Penn State Univ Embedded & Mobile Comp Design Ctr University Pk PA 16802 USA Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

This paper describes a new architecture for discrete cosine transform (DCT)-based motion estimation and compensation. Previous methods do not take sufficient advantage of the sparseness of two-dimensional (2-D) DCT coefficients to reduce execution time. We first derive a recursion equation for transform domain motion estimation;we then use it to develop a wave-front array processor consisting of highly regular, parallel, and pipelined processing elements that more efficiently performs motion estimation. In addition, we show that the recursion equation enables motion predicted images with different frequency bands, for example, from the images with low-frequency components to the images with low- and high-frequency components. The wavefront array processor can reconfigure to different motion estimation algorithms, such as logarithmic search and three step search, without architectural modifications. These properties can be effectively used to reduce the energy required for video encoding and decoding. Simulation results on video sequences of different characteristics show that the proposed architecture achieves a significant reduction in computational complexity and processing time, with comparable performance to spatial domain approaches with respect to the peak signal to noise ratio (PSNR) and the compression ratio.

关键词： motion compensation motion estimation recursion equation sparse matrix computation video compression wavefront array processor

来源：评论

学校读者我要写书评

暂无评论

A PARALLEL ALGORITHM FOR sparse SYMBOLIC CHOLESKY FACTORIZATION ON A MULTIPROCESSOR

引用

PARALLEL COMPUTING 1988年第2期7卷 199-210页

作者： ZMIJEWSKI, E GILBERT, JR Computer Science Department Cornell University Ithaca NY 14853 U.S.A.

We develop an algorithm for computing the symbolic Cholesky factorization of a large sparse symmetric positive definite matrix. The algorithm is intended for a message-passing multiprocessor system, such as the hypercube, and is based on the concept of elimination forest. In addition, we provide an algorithm for computing these forests along with a discussion of the algorithm's complexity and a proof of its correctness.

关键词： Cholesky factorization elimination forest Linear algebra message-passing multiprocessor sparse matrix computation

来源：评论

学校读者我要写书评

暂无评论

A NEW CLASS OF AMG INTERPOLATION METHODS BASED ON matrix-matrix MULTIPLICATIONS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2021年第5期43卷 S540-S564页

作者： LI, Ruipeng Sjogreen, Bjorn Yang, Ulrike Meier Ctr Appl Sci Comp Lawrence Livermore Natl Lab Livermore CA 94551 USA

A new class of distance-two interpolation methods for algebraic multigrid (AMG) that can be formulated in terms of sparse matrix-matrix multiplications is presented and analyzed. Compared with similar distance-two prolongation operators [H. De Sterck et al., Numer. Linear Algebra Appl., 15 (2008), pp. 115-139], the proposed algorithms exhibit improved efficiency and portability to various computing platforms, since they allow one to easily exploit existing high-performance sparse matrix kernels. The new interpolation methods have been implemented in hypre [R. D. Falgout and U. M. Yang, hypre: A library of high performance preconditioners, in computational Science - ICCS 2002, P. M. A. Sloot et al., eds., Springer, Berlin, Heidelberg, 2002, pp. 632-641], a widely used parallel multigrid solver library. With the proposed interpolations, the overall time of hypre's BoomerAMG setup can be considerably reduced, while sustaining equivalent, sometimes improved, convergence rates. Numerical results for a variety of test problems on parallel machines are presented that support the superiority of the proposed interpolation operators over the existing ones in hypre.

关键词： AMG interpolation sparse matrix computation parallel and distributed computing

来源：评论

学校读者我要写书评

暂无评论

An evaluation of limited-memory sparse linear solvers for thermo-mechanical applications

引用

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING 2008年第11期74卷 1690-1715页

作者： Teranishi, Keita Raghavan, Padma Sun, Jun Michaleris, Panagiotis Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Penn State Univ Dept Mech & Nucl Engn University Pk PA 16802 USA

We consider the performance of sparse linear solvers for problems that arise from thermo-mechanical applications. Such problems have been solved using sparse direct schemes that enable robust solution at the expense of memory requirements that grow non-linearly with the dimension of the coefficient matrix. In this paper, we consider a class of preconditioned iterative solvers as a limited-memory alternative to direct solution schemes. However, such preconditioned iterative solvers typically exhibit complex trade-offs between reliability and performance. We therefore characterize such trade-offs for systems from thermo-mechanical problems by considering several preconditioning schemes including multilevel methods and those based on sparse approximate inversion and incomplete matrix factorization. We provide an analysis of computational costs and memory requirements for model thermo-mechanical problems, indicating that certain incomplete factorization schemes can achieve good performance. We also provide empirical evaluations that corroborate our analysis and indicate the relative effectiveness of different solution schemes. Our results indicate that our drop-threshold incomplete Cholesky preconditioning is more robust, efficient and flexible than other popular preconditioning schemes. In addition, we propose preconditioner reuse to amortize preconditioner construction cost over a sequence of linear systems that arise from non-linear solutions in a plastic regime. Copyright (c) 2007 John Wiley & Sons, Ltd.

关键词： numerical linear algebra thermo-mechanical analysis finite element analysis sparse matrix computation

来源：评论

学校读者我要写书评

暂无评论

PARALLEL SYMBOLIC FACTORIZATION OF sparse LINEAR-SYSTEMS

引用

PARALLEL COMPUTING 1990年第2期14卷 151-162页

作者： GILBERT, JR HAFSTEINSSON, H UNIV ICELAND INST SCIIS-107 REYKJAVIKICELAND

The Cholesky factorization of a sparse matrix A can introduce new nonzeros into the factor matrix. We present an efficient CRCW parallel algorithm to find this fill. Our algorithm takes O(log 2 n ) time using m∗ processors, where m∗ is the number of nonzeros in the Cholesky factor of A . The algorithm has two stages. First it finds A 's elimination tree, and then uses it to compute the fill. The part of the algorithm that finds the elimination tree runs in O(log 2 n ) time using m processors, where m is the number of nonzeros in A .

关键词： elimination trees Linear algebra parallel algorithms sparse matrix computation

来源：评论

学校读者我要写书评

暂无评论

Fast Cholesky factorization for interior point methods of linear programming

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1996年第4-5期31卷 49-54页

作者： Meszaros, C Computer and Automation Research Institute Hungarian Academy of Sciences Department of Operations Research and Decision Systems H-1518 Budapest P.O. Box 63 Hungary

Every iteration of an interior point method of large scale linear programming requires computing at least one orthogonal projection. In practice, Cholesky decomposition seems to be the most efficient and sufficiently stable method. We studied the 'column orientated' or 'left looking 'sparse variant of the Cholesky decomposition, which is a very popular method in large scale optimization. We show some techniques such as using supernodes and loop unrolling for improving the speed of computation. We show numerical results on a wide variety of large scale, real-life linear programming problems.

关键词： sparse matrix computation interior point methods Cholesky factorization supernodes

来源：评论

学校读者我要写书评

暂无评论

Vectorizing sparse matrix computations with partially-strided codelets 22

Vectorizing sparse matrix computations with partially-stride...

引用

Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

作者： Kazem Cheshmi Zachary Cetinic Maryam Mehri Dehnavi University of Toronto Toronto Canada

The compact data structures and irregular computation patterns in sparse matrix computations introduce challenges to vectorizing these codes. Available approaches primarily vectorize strided computation regions of a sparse code. In this work, we propose a locality-based codelet mining (LCM) algorithm that efficiently searches for strided and partially strided regions in sparse matrix computations for vectorization. We also present a classification of partially strided codelets and a differentiation-based approach to generate codelets from memory accesses in the sparse computation. LCM is implemented as an inspector-executor framework called LCM I/E that generates vectorized code for the sparse matrix-vector multiplication (SpMV), sparse matrix times dense matrix (SpMM), and sparse triangular solver (SpTRSV). LCM I/E outperforms the MKL library with an average speedup of 1.67×, 4.1×, and 1.75× for SpMV, SpTRSV, and SpMM, respectively. It is also faster than the state-of-the-art inspector-executor framework Sympiler [1] for the SpTRSV kernel with an average speedup of 1.9×.

关键词： parallel programming vectorization sparse matrix computation polyhedral analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：