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

2 SPACE-SAVING algorithms FOR COMPUTING THE PERMUTED TRANSPOSE OF A sparse-matrix

ADVANCES IN ENGINEERING SOFTWARE 1993年第1期17卷 49-60页

作者： CAMERON, F TAMPERE UNIV TECHNOL CONTROL ENGN LABSF-33101 TAMPEREFINLAND

Given an m x n sparse matrix A having n(a) nonzeros and a permutation matrix P, we consider the problem of finding (PA)T in a space-saving manner. Two algorithms, TRANSPERM1 and TRANSPERM2, are presented. Both algorithms make use of the in-place inversion of permutation vectors. To save even more space TRANSPERM1 forms a piecewise linear model of the nonzero distribution. The computational complexity of TRANSPERM2 is O(n(a), n, m). For a particularly treacherous nonzero distribution we derive an upper bound for the complexity of TRANSPERM1 of O(n(a), taun(a)n/n(l), m, n, n(l)), where n(l) is the number of intervals in the piecewise model and tau less-than-or-equal-to 1/2. These two algorithms were compared with Gustavson's efficient HALFPERM algorithm.3 We expected our algorithms to be slower than HALFPERM since they were written with the intention of saving space. In tests on 21 matrices, HALFPERM was on average 2.5 times faster than TRANSPERM1 and 1.6 times faster than TRANSPERM2. However, for these 21 matrices, TRANSPERM1's storage requirements were on average only 51% of HALFPERM's, and TRANSPERM2's requirements were only 67% of HALFPERM's.

关键词： sparse matrix PERMUTED TRANSPOSE sparse matrix algorithms sparse matrix STORAGE REQUIREMENTS PERMUTATION VECTOR INVERSION

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for placing large entries along the diagonal of a sparse matrix

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2010年第3期235卷 756-764页

作者： Kundeti, Vamsi Rajasekaran, Sanguthevar Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

Solving a sparse system of linear equations Ax = b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g.. Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(vertical bar V vertical bar + vertical bar E vertical bar) to O(vertical bar V vertical bar), where vertical bar V vertical bar is the order of the matrix A and vertical bar E vertical bar is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duffs algorithm) for sparse matrices with at least a million non-zeros. (C) 2010 Elsevier B.V. All rights reserved.

关键词： sparse matrix algorithms Pre ordering sparse matrix Diagonally dominant sparse matrix Weighted matching algorithms Bipartite matching Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Application-based fault tolerance techniques for sparse matrix solvers

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2018年第5期32卷 627-640页

作者： McIntosh-Smith, Simon Hunt, Rob Price, James Vesztrocy, Alex Warwick Univ Bristol High Performance Comp Bristol Avon England Univ Bristol Bristol Avon England Univ Bristol High Performance Comp Grp Bristol Avon England UCL London England

High-performance computing systems continue to increase in size in the quest for ever higher performance. The resulting increased electronic component count, coupled with the decrease in feature sizes of the silicon manufacturing processes used to build these components, may result in future exascale systems being more susceptible to soft errors caused by cosmic radiation than in current high-performance computing systems. Through the use of techniques such as hardware-based error-correcting codes and checkpoint-restart, many of these faults can be mitigated at the cost of increased hardware overhead, run-time, and energy consumption that can be as much as 10-20%. Some predictions expect these overheads to continue to grow over time. For extreme scale systems, these overheads will represent megawatts of power consumption and millions of dollars of additional hardware costs, which could potentially be avoided with more sophisticated fault-tolerance techniques. In this paper we present new software-based fault tolerance techniques that can be applied to one of the most important classes of software in high-performance computing: iterative sparse matrix solvers. Our new techniques enables us to exploit knowledge of the structure of sparse matrices in such a way as to improve the performance, energy efficiency, and fault tolerance of the overall solution.

关键词： Fault tolerance sparse matrix algorithms exascale single event upsets error-correcting bit-flips

来源：评论

学校读者我要写书评

暂无评论

PREDICTING STRUCTURE IN sparse-matrix COMPUTATIONS

引用

SIAM JOURNAL ON matrix ANALYSIS AND APPLICATIONS 1994年第1期15卷 62-79页

作者： GILBERT, JR UNIV ICELAND REYKJAVIKICELAND UNIV MINNESOTA INST MATH & APPLICATMINNEAPOLISMN 55455

Many sparse matrix algorithms-for example, solving a sparse system of linear equations-begin by predicting the nonzero structure of the output of a matrix computation from the nonzero structure of its input. This paper is a catalog of ways to predict nonzero structure. It contains known results for some problems, including various matrix factorizations, and new results for other problems, including some eigenvector computations.

关键词： sparse matrix algorithms GRAPH THEORY matrix FACTORIZATION SYSTEMS OF LINEAR EQUATIONS EIGENVECTORS

来源：评论

学校读者我要写书评

暂无评论

Exploiting Spatial Information in Datasets To Enable Fault Tolerant sparse matrix Solvers

Exploiting Spatial Information in Datasets To Enable Fault T...

引用

IEEE International Conference on Cluster Computing (CLUSTER)

作者： Hunt, Rob McIntosh-Smith, Simon Univ Bristol Dept Comp Sci Bristol Avon England

ISBN: (纸本)9781467365987

High-performance computing (HPC) systems continue to increase in size in the quest for ever higher performance. The resulting increased electronic component count, coupled with the decrease in feature sizes of the silicon manufacturing processes used to build these components, will result in future Exascale systems being more susceptible to soft errors caused by cosmic radiation than current HPC systems. Through the use of techniques such as hardware-based error correcting codes (ECC) and checkpoint-restart, many of these faults can be mitigated, but at the cost of increased hardware overhead, run-time, and energy consumption that can be as much as 10-20%. For extreme scale systems, these overheads will represent megawatts of power consumption and millions of dollars of additional hardware cost, which could potentially be avoided with more sophisticated fault-tolerance techniques. In this paper we present a new software-based fault tolerance technique that can be applied to one of the most important classes of software in HPC: sparse matrix solvers. Our new technique enables us to exploit knowledge of the structure of sparse matrices in such a way as to improve the performance, energy efficiency and fault tolerance of the overall solution.

关键词： fault tolerance sparse matrix algorithms Exascale single event upsets error-correcting bit-flips

来源：评论

学校读者我要写书评

暂无评论

Algorithm 1021: SPEX Left LU, Exactly Solving sparse Linear Systems via a sparse Left-looking Integer-preserving LU Factorization

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2022年第2期48卷 1–23页

作者： Lourenco, Christopher Chen, Jinhao Moreno-Centeno, Erick Davis, Timothy A. US Naval Acad Dept Math 121 Blake Rd Annapolis MD 21402 USA Texas A&M Univ Dept Comp Sci & Engn 3112 TAMU College Stn TX 77843 USA Inst Tecnol Autonomo Mexico Mexico City DF Mexico Texas A&M Univ Dept Ind & Syst Engn 3131 TAMU College Stn TX 77843 USA

SPEX Left LU is a software package for exactly solving unsymmetric sparse linear systems. As a component of the sparse exact (SPEX) software package, SPEX Left LU can be applied to any input matrix, A, whose entries are integral, rational, or decimal, and provides a solution to the system Ax = b, which is either exact or accurate to user-specified precision. SPEX Left LU preorders the matrix A with a user-specified fill-reducing ordering and computes a left-looking LU factorization with the special property that each operation used to compute the L and U matrices is integral. Notable additional applications of this package include benchmarking the stability and accuracy of state-of-the-art linear solvers and determining whether singular-to-double-precision matrices are indeed singular. Computationally, this article evaluates the impact of several novel pivoting schemes in exact arithmetic, benchmarks the exact iterative solvers within Linbox, and benchmarks the accuracy of MATLAB sparse backslash. Most importantly, it is shown that SPEX Left LU outperforms the exact iterative solvers in run time on easy instances and in stability as the iterative solver fails on a sizeable subset of the tested (both easy and hard) instances. The SPEX Left LU package is written in ANSI C, comes with a MATLAB interface, and is distributed via GitHub, as a component of the SPEX software package, and as a component of Suitesparse.

关键词： Exactly solving linear systems sparse linear systems sparse matrix algorithms roundoff errors exact matrix factorization

来源：评论

学校读者我要写书评

暂无评论

EXACT SOLUTION OF sparse LINEAR SYSTEMS VIA LEFT-LOOKING ROUNDOFF-ERROR-FREE LU FACTORIZATION IN TIME PROPORTIONAL TO ARITHMETIC WORK

引用

SIAM JOURNAL ON matrix ANALYSIS AND APPLICATIONS 2019年第2期40卷 609-638页

作者： Lourenco, Christopher Escobedo, Adolfo R. Moreno-Centeno, Erick Davis, Timothy A. Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA Arizona State Univ Sch Comp Informat & Decis Syst Engn Tempe AZ 85281 USA Inst Tecnol Autonomo Mexico Dept Ind & Operat Engn Ciudad De Mexico 01080 Mexico Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

The roundoff-error-free (REF) LU factorization, along with the REF forward and backward substitution algorithms, allows a rational system of linear equations to be solved exactly and efficiently. The REF LU factorization framework has two key properties: all operations are integral, and the size of each entry is bounded polynomially-a bound that rational arithmetic Gaussian elimination achieves only via the use of computationally expensive greatest common divisor operations. This paper develops a sparse version of REF LU, termed the sparse Left-looking Integer-Preserving (SLIP) LU factorization, which exploits sparsity while maintaining integrality of all operations. In addition, this paper derives a tighter polynomial bound on the size of entries in L and U and shows that the time complexity of SLIP LU is proportional to the cost of the arithmetic work performed. Last, SLIP LU is shown to significantly outperform a modern full-precision rational arithmetic LU factorization approach on a set of real world instances. In all, SLIP LU is a framework to efficiently and exactly solve sparse linear systems.

关键词： exact linear solutions LU factorizations roundoff errors solving linear systems sparse matrix algorithms sparse IPGE word length sparse linear systems

来源：评论

学校读者我要写书评

暂无评论

EXACTLY SOLVING sparse RATIONAL LINEAR SYSTEMS VIA ROUNDOFF-ERROR-FREE CHOLESKY FACTORIZATIONS

引用

SIAM JOURNAL ON matrix ANALYSIS AND APPLICATIONS 2022年第1期43卷 439-463页

作者： Lourenco, Christopher J. Moreno-Centeno, Erick United States Naval Acad Dept Math Annapolis MD 21402 USA Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77483 USA

Exactly solving sparse symmetric positive definite (SPD) linear systems is a key problem in mathematics, engineering, and computer science. This paper derives two new sparse roundoff-error-free (REF) Cholesky factorization algorithms which exactly solve sparse SPD linear systems Ax = b, where A is an element of Qnxn and x,b is an element of Qnxp. The key properties of these factorizations are that (1) they exclusively use integer-arithmetic and (2) in the bit-complexity model, they solve the linear system Ax = b in time proportional to the cost of the integer-arithmetic operations. Namely, the overhead related to data structures and ancillary operations (those not strictly required to perform the factorization) is subsumed by the cost of the integer-arithmetic operations that are essential/intrinsic to the factorization. Notably, to date our algorithms are the only exact algorithm for solving SPD linear systems with this asymptotically efficient complexity bound. Computation-ally, we show that the novel factorizations are faster than both sparse rational-arithmetic LDL and sparse exact LU factorization. Altogether, the derived sparse REF Cholesky factorizations present a framework to solve any rational SPD linear system exactly and efficiently.

关键词： Cholesky factorization exact factorization sparse matrix algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithm 1050: SPEX Cholesky, LDL, and Backslash for Exactly Solving sparse Linear Systems

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2024年第4期50卷 1-29页

作者： Mejia-domenzain, Lorena Chen, Jinhao Lourenco, Christopher Moreno-centeno, Erick Davis, Timothy a Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77840 USA Texas A&M Univ Dept Comp Sci & Engn College Stn TX USA US Naval Acad Dept Math Annapolis MD USA

SPEX Cholesky, SPEX LDL, and SPEX Backslash are software packages for exactly solving sparse linear systems, Ax = b . SPEX Cholesky, used for symmetric positive definite (SPD) systems, computes an integral Cholesky factorization to solve the system Ax = b in time proportional to arithmetic work-to date the only algorithm for SPD linear systems with this property. SPEX LDL extends SPEX Cholesky for symmetric negative definite and symmetric indefinite matrices with exclusively non-zero leading principal minors. SPEX Backslash is a general-purpose exact solver that automatically determines the best ordering and factorization to exactly solve the system Ax = b . Computationally, we test the accuracy of MATLAB sparse backslash, the state-of-the-art collection of sparse matrix solvers, revealing it is near perfect for 87% of the tested instances. In addition, we show that SPEX Cholesky outperforms alternate exact solvers in runtime;specifically, SPEX Cholesky outperforms the exact solver Linbox and exact LU factorization on 70% and 92% of tested instances, respectively. Each of SPEX Cholesky, SPEX LDL, and SPEX Backslash is implemented in C and is accompanied by easy-to-use Python and MATLAB interfaces. They are distributed via GitHub, as a component of the SPEX software package, and as component of Suitesparse.

关键词： exactly solving linear systems sparse linear systems sparse matrix algorithms roundoff errors exact matrix factorization

来源：评论

学校读者我要写书评

暂无评论

Balancing sparse matrices for computing eigenvalues

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2000年第1-3期309卷 261-287页

作者： Chen, TY Demmel, JW Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

Applying a permuted diagonal similarity transform DPAP(T)D(-1) to a matrix A before calculating its eigenvalues can improve the speed and accuracy with which the eigenvalues are computed. This is often called balancing. This paper describes several balancing algorithms for sparse matrices and compares them against each other and the traditional dense algorithm. We first discuss our sparse implementation of the dense algorithm;our code is faster than the dense algorithm when the density of the matrix is no more than approximately .5, and is much faster for large, sparse matrices. We next describe a set of randomized balancing algorithms for matrices that are not given explicitly, i.e. given a vector x, we can compute only Ax and perhaps A(T)x. We motivate these Krylov-based algorithms using Perron-Frobenius theory. Results are given comparing the Krylov-based algorithms to each other and to the sparse and dense direct balancing algorithms, looking at norm reduction, running times, and the accuracy of eigenvalues computed after a matrix is balanced. We conclude that sparse balancing algorithms are efficient preconditioners for eigensolvers. (C) 2000 Elsevier Science Inc. All rights reserved.

关键词： balancing norm minimization accurate eigenvalues sparse matrix algorithms

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：