Search

International audience; We investigate a special class of data sparse rank-structured matrices that combine a flat block low-rank (BLR) partitioning with the use of shared (called nested in the hierarchical case) bases. This format is to H 2 matrices what BLR is to H matrices: we therefore call it the BLR 2 matrix format. We present algorithms for the construction and LU factorization of BLR 2 matrices, and perform their cost analysis-both asymptotically and for a fixed problem size. With weak admissibility, BLR 2 matrices reduce to block separable matrices (the flat version of HBS/HSS). Our analysis and numerical experiments reveal some limitations of BLR 2 matrices with weak admissibility, which we propose to overcome with two approaches: strong admissibility, and the use of multiple shared bases per row and column.

International audience; Matrices coming from elliptic partial differential equations have been shown to have alow-rank property: well-defined off-diagonal blocks of their Schur complements can be approximatedby low-rank products. Given a suitable ordering of the matrix which gives the blocks a geometricalmeaning, such approximations can be computed using an SVD or a rank-revealing QR factorization.The resulting representation offers a substantial reduction of the memory requirement and givesefficient ways to perform many of the basic dense linear algebra operations. Several strategies,mostly based on hierarchical formats, have been proposed to exploit this property. We study asimple, nonhierarchical, low-rank format called block low-rank (BLR) and explain how it can be usedto reduce the memory footprint and the complexity of sparse direct solvers based on the multifrontalmethod. We present experimental results on matrices coming from elliptic PDEs and from variousother applications. We show that even if BLR-based factorizations are asymptotically less efficientthan hierarchical approaches, they still deliver considerable gains. The BLR format is compatiblewith numerical pivoting, and its simplicity and flexibility make it easy to use in the context of ageneral purpose, algebraic solver.

In this paper we provide a robust reordering scheme for sparse matrices. The scheme relies on the notion of multisection, a generalization of bisection. The reordering strategy is demonstrated to have consistently good performance in terms of fill reduction when compared with multiple minimum degree and generalized nested dissection. Experimental results show that by using multisection, we obtain an ordering which is consistently as good as or better than both for a wide spectrum of sparse problems.

In this paper, we consider the use of the Dulmage--Mendelsohn decomposition and network flow on bipartite graphs to improve a graph bisection partition. Given a graph partition [B, W, S] with a vertex separator S and two disconnected components B and W, different strategies are considered based on the Dulmage--Mendelsohn decomposition to reduce the separator size |S| and/or the imbalance between B and W. For the case when the vertices are weighted, we relate this to the bipartite network flow problem. A further enhancement to improve a partition is to generalize the bipartite network to a general network and then solve a max-flow problem. We demonstrate the utility of these improvement techniques on a set of sparse test matrices, where we find top-level separators, nested dissection, and multisection orderings.

In this paper we introduce a three-step approach to find a vertex bisector of a graph. The first step finds adomain decomposition of the graph, consisting of a set of domains and a multisector. Eachdomain is a connected subgraph, and themultisector contains the remaining vertices that separate the domains from each other. The second step uses a block variant of the Kernighan-Lin scheme to find a bisector that is a subset of the multisector. The third step improves the bisector by bipartite graph matching. Experimental results show this domain decomposition method finds graph partitions that compare favorably with a state-of-the-art multilevel partitioning scheme in both quality and execution time.

This paper presents a column-oriented distributed algorithm for factoring a large sparse symmetric positive definite matrix on a local-memory parallel processor. Processors cooperate in computing each column of the Cholesky factor by calculating independent updates to the corresponding column of the original matrix. These updates are sent in a fan-in manner to the processor assigned to the column, which then completes the computation. Experimental results on an Intel iPSC/2 hypercube demonstrate that the method is effective and achieves good speedups.

Sparse matrix computations arise in many scientific and engineering applications, but their performance is limited by the growing gap between processor and memory speed. In this paper, we present a case study of an important sparse matrix triple product problem that commonly arises in primal-dual optimization method. Instead of a generic two-phase algorithm, we devise and implement a single pass algorithm that exploits the block diagonal structure of the matrix. Our algorithm uses fewer floating point operations and roughly half the memory of the two-phase algorithm. The speed-up of the one-phase scheme over the two-phase scheme is 2.04 on a 900 MHz Intel Itanium-2, 1.63 on an 1 GHz Power-4, and 1.99 on a 900 MHz Sun Ultra-3.

There are two classic column-based Cholesky factorization methods, the fan-out method that communicates factor columns among processors, and the fan-in method that communicates aggregate update columns among processors. In this paper we show that these two very different methods are members of a “fan-both” algorithm family.

The solution of large sparse systems of linear is an important application of parallel computers. In this paper, we give a unified presentation and compare the performance of three distributed schemes to compute the Cholesky factor of a large sparse symmetric positive definite matrix on a local-memory parallel processor. (kr)