NEARLY OPTIMAL BLOCK-JACOBI PRECONDITIONING

The goal of Jacobi preconditioning DAD of a symmetric positive definite matrix A by a diagonal matrix D is to choose D to minimize the condition number k(DAD). In 1969, van der Sluis proved that choosing D so that the diagonal entries of DAD are all ones reduces k(DAD) to within a factor of the minimum possible, where the factor depends on both the dimension n and the norms used to define the condition number. We extend this result in two ways to block-Jacobi preconditioning, where D is a block-diagonal matrix with blocks of given sizes, and we consider DADT instead of DAD to maintain the symmetric positive definite (spd) property. First, we extend van der Sluis's original bound to include block-Jacobi. Second, we define a new norm in which choosing D so that the corresponding diagonal blocks of DADT are identity matrices minimizes the condition number. We use this to show that the condition number in the 2-norm of this optimally scaled DADT is at least as large as the condition number in the new norm, and at most a factor d2 larger, where d is the number of diagonal blocks. We give an example where the optimal 2-norm condition number nearly attains this new upper bound, which for this example is tighter than van der Sluis's bound by a factor equal to the matrix dimension. Finally, all these results generalize to the case of one-sided scaling DB of a full row-rank matrix B.