TECHNICAL REPORT BU-CE-0701, BILKENT UNIVERSITY,
DEPARTMENT OF COMPUTER ENGINEERING

TITLE: Obtaining Triangular Diagonal Blocks in Sparse Matrices Using
Cutsets

AUTHOR: Tugrul Dayar

ABSTRACT: The paper proposes an algorithm which computes a (2 x 2) block
partition of an irreducible, sparse matrix with a zero-free diagonal so
that one of the diagonal blocks is triangular. The algorithm works by
computing a cutset of the directed graph associated with the off-diagonal
part of the matrix and is linear in the number of nonzeros therein. The
proposed algorithm is then extended to reducible, sparse matrices with a
zero-free diagonal. Experiments on benchmark unsymmetric matrices show
that, in many cases the order of the triangular block can be increased by
using another algorithm for computing cutsets from the literature, which
is based on a greedy randomized adaptive search procedure; however, this
is not efficient timewise unless the matrix is relatively small. A block
iterative solver based on the partition returned by the proposed
algorithm is compared with an industrial strength direct solver for time,
space, and accuracy. Results indicate that there are cases in which it is
advantageous to compute and use block partitions based on cutsets.