Fast structured LU factorization for nonsymmetric matrices

In this paper, an approximate LU factorization algorithm is developed for nonsymmetric matrices based on the hierarchically semiseparable matrix techniques. It utilizes a technique involving orthogonal transformations and approximations to avoid the explicit computation of the Schur complement in each factorization step. A modified compression method is further developed for the case when some diagonal blocks have small singular values. The complexity of the methods proposed in this paper is analyzed and shown to be $O(N^2k)$ , where $N$ is the dimension of matrix and $k$ is the maximum off-diagonal (numerical) rank. Depending on the accuracy and efficiency requirements in the approximation, this factorization can be used either as a direct solver or a preconditioner. Numerical results from applications are included to show the efficiency of our method.