The solution of large-scale linear systems in computational science and engineering requires efficient solvers and preconditioners. Often, the most effective such techniques are those based on multilevel splittings of the problem. In this paper, we consider the problem of partitioning both symmetric and nonsymmetric matrices based solely on algebraic criteria. A new algorithm is proposed that combines attractive features of two previous techniques proposed by the authors. It offers rigorous guarantees of certain properties of the partitioning, yet is naturally compatible with the threshold based dropping known to be effective for incomplete factorizations. Numerical results show that the new partitioning scheme leads to improved results for a variety of problems. The effects of further matrix reordering within the fine-scale block are also considered.