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.