Nearly Optimal Block-Jacobi Preconditioning
The goal of Jacobi preconditioning π·β’π΄β’π·π·β’π΄β’π· of a symmetric positive definite matrix π΄π΄ by a diagonal matrix π·π· is to choose π·π· to minimize the condition number π β‘(π·β’π΄β’π·)π β‘(π·β’π΄β’π·). In 1969, van der Sluis proved that choosing π·π· so that the diagonal entries of π·β’π΄β’π·π·β’π΄β’π· are all ones reduces π β‘(π·β’π΄β’π·)π β‘(π·β’π΄β’π·) to within a factor of the minimum possible, where the factor depends on both the dimension ππ and the norms used to define the condition number. We extend this result in two ways to block-Jacobi preconditioning, where π·π· is a block-diagonal matrix with blocks of given sizes, and we consider π·β’π΄β’π·ππ·β’π΄β’π·π instead of π·β’π΄β’π·π·β’π΄β’π· 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 π·π· so that the corresponding diagonal blocks of π·β’π΄β’π·ππ·β’π΄β’π·π are identity matrices minimizes the condition number. We use this to show that the condition number in the 2-norm of this optimally scaled π·β’π΄β’π·ππ·β’π΄β’π·π is at least as large as the condition number in the new norm, and at most a factor π2π2 larger, where ππ 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 π·β’π΅π·β’π΅ of a full row-rank matrix π΅π΅.