Conditioning analysis of incomplete Cholesky factorizations with orthogonal dropping Page: 3 of 37
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
quotient of its largest and smallest eigenvalues), as required to estimate the conver-
gence rate of iterative methods such as conjugate gradient [1, 14, 22]. The bound
involves quantities which only depend on the individual orthogonal approximations
and in a way measure their accuracy.
Now, the algorithms in  and  modify different groups of rows during the
approximation steps. This may further lead to an improved condition estimate
involving the same accuracy measures if the modified rows (and the rows with
lower indices) are no longer modified for the few following steps. The ideal case
when only the newly computed rows are modified at each step (and, hence, each
row is modified at most once) is of particular interest. This case is referred to as
one-level for reasons which are made clear below. The related estimate is shown
to be sharp in that, for every set of accuracy values, there exist a matrix and a
corresponding incomplete factorization preconditioner, obtained using orthogonal
dropping, that allow to reach the bound.
We note that a related accuracy measure has been introduced in . The
analysis there is however applied in a rather model case when only one approxi-
mation step is performed. In this context, for instance, no distinction can be made
between a general and a "localized" dropping mentioned above, as the bounds in
both cases lead to the same condition number estimate.
Another particular case arises when the approximated blocks of the factor are
set to zero, and the resulting preconditioner corresponds to a block-diagonal part of
A. The accuracy measures then coincide with so-called CBS constants, which are
commonly used in the eigenvalue estimates of a block-diagonally preconditioned
system. Again, the case when the preconditioner has 2 x 2 blockdiagonal form is
well understood [2, 1]; however, the extension to block-diagonal preconditioners
with multiple blocks which arise form our analysis leads to a better bound than
one could obtain by recursively applying the 2 x 2 estimate. In addition, the
above-mentioned sharpness property carries over to the block-diagonal case (and,
for simplicity, we only prove this property for block-diagonal preconditioners).
Eventually, our analysis is illustrated with the factorization algorithms in ,
 and the one-level variant in the context of model problem arising from a low-
order discretization of a second-order PDE. Numerical experiments reveal that all
the considered preconditioners have similar conditioning properties, and further,
that the bound for the one-level variant allows an accurate prediction of their
condition number. On the other hand, based on the analysis, the approximation
schemes are modified to keep the condition number bounded independently of the
problem size; their effectiveness is also assessed in the model problem context.
The reminder of the paper is organized as follows. In Section 2 we introduce
our generic incomplete Cholesky factorization with orthogonal dropping and relate
it to the existing methods. The bounds on the condition number are presented in
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Napov, Artem. Conditioning analysis of incomplete Cholesky factorizations with orthogonal dropping, article, March 16, 2012; Berkeley, California. (https://digital.library.unt.edu/ark:/67531/metadc830695/m1/3/: accessed April 26, 2019), University of North Texas Libraries, Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.