ePubs
The open archive for STFC research publications
Home
About ePubs
Content Policies
News
Help
Privacy/Cookies
Suggest an Enhancement
Contact ePubs
Full Record Details
DOI
10.5286/raltr.2010027
Persistent URL
http://purl.org/net/epubs/work/53601
Record Status
Checked
Record Id
53601
Title
On computing inverse entries of a sparse matrix in an out-of-core environment
Contributors
PR Amestoy (Tolouse U.)
,
IS Duff (STFC Rutherford Appleton Lab.)
,
Y Robert (Centre National de la Recherche Scientifique)
,
F-H Rouet (Tolouse U.)
,
B Ucar (Centre National de la Recherche Scientifique)
Abstract
The inverse of an irreducible sparse matrix is structurally full, so that it is impractical to think of computing or storing it. However, there are several applications where a subset of the entries of the inverse is required. Given a factorization of the sparse matrix held in outof- core storage, we show how to compute such a subset efficiently, by accessing only parts of the factors. When there are many inverse entries to compute, we need to guarantee that the overall computation scheme has reasonable memory requirements, while minimizing the cost of loading the factors. This leads to a partitioning problem that we prove is NPcomplete. We also show that we cannot get a close approximation to the optimal solution in polynomial time. We thus need to develop heuristic algorithms, and we propose: (i) a lower bound on the cost of an optimum solution; (ii) an exact algorithm for a particular case; (iii) two other heuristics for a more general case; and (iv) hypergraph partitioning models for the most general setting. We illustrate the performance of our algorithms in practice using the MUMPS software package on a set of real-life problems as well as some standard test matrices. We show that our techniques can improve the execution time by a factor of 50.
Organisation
CSE
,
CSE-NAG
,
STFC
Keywords
graphs and hypergraphs
,
direct methods for linear systems and matrix inversion
,
multifrontal method
,
sparse matrices
Funding Information
Related Research Object(s):
Licence Information:
Language
English (EN)
Type
Details
URI(s)
Local file(s)
Year
Report
RAL Technical Reports
RAL-TR-2010-027. 2010.
RAL-TR-2010-027.pdf
2010
Showing record 1 of 1
Recent Additions
Browse Organisations
Browse Journals/Series
Login to add & manage publications and access information for OA publishing
Username:
Password:
Useful Links
Chadwick & RAL Libraries
SHERPA FACT
SHERPA RoMEO
SHERPA JULIET
Journal Checker Tool
Google Scholar