An Introduction To ML(n)BiCGStab
Free (open access)
331 - 342
M. C. Yeung
ML(n)BiCGStab is a Krylov subspace method for the solution of large, sparse and non-symmetric linear systems. In theory, it is a method that lies between the well-known BiCGStab and GMRES/FOM. In fact, when n = 1, ML(1)BiCGStab is BiCGStab and when n = N, ML(N)BiCGStab is GMRES/FOM where N is the size of the linear system. Therefore, ML(n)BiCGStab is a bridge that connects the Lanczos-based BiCGStab and the Arnoldi-based GMRES/FOM. In computation, ML(n)BiCGStab can be much more stable and convergemuch faster than BiCGStab when a problem with ill-condition is solved. We have tested ML(n)BiCGStab on the standard oil reservoir simulation test data called SPE9 and found that ML(n)BiCGStab reduced the total computational time by more than 60% when compared to BiCGStab. Tests made on the data from Matrix Market also support the superiority of ML(n)BiCGStab over BiCGStab. Because of the O(N2) storage requirement in the full GMRES, one has to adopt a restart strategy to get the storage under control when GMRES is implemented. In comparison, ML(n)BiCGStab is a method with only O(nN) storage requirement and therefore it does not need a restart strategy. In this paper, we introduce ML(n)BiCGStab (in particular, a new algorithm involving A-transpose), its relations to some existing methods and its implementations. Keywords: CGS, BiCGStab, ML(n)BiCGStab, multiple starting Lanczos, Krylov subspace, iterative methods, linear systems. 1 Introduction ML(n)BiCGStab is a Krylov subspace method for the solution of the linear system Ax = b (1) whereA ∈ CN×N and b ∈ CN. It was introduced by Yeung and Chan  in 1999 and its algorithms were recently reformulated by Yeung . ML(n)BiCGStab is
CGS, BiCGStab, ML(n)BiCGStab, multiple starting Lanczos, Krylov subspace, iterative methods, linear systems.