[Trilinos-Users] Block-Davidson usage advice needed

[Chris Baker]

Gerry,

For the block Davidson solver manager, there are four relevant parameters
here:

   - "Block Size" determines the block size of the algorithm, i.e., the
   number of eigenvector estimates and the number of vectors by which the
   search basis is expanded at each iteration
   - "Num Blocks" determines the number of blocks for which the basis is
   allocated. The number of vectors in the basis is the number of blocks
   multiplied by the block size. Because the basis is orthogonal (and therefore
   full-rank), it is limited to the dimension of the eigenvalue problem. In
   practice, however, the total basis size is typically chosen much smaller
   because of demands on memory and the cost of orthogonalization associated
   with building such a large basis. This is balanced against the fact that a
   larger basis gives faster convergence (with respect to number of
   iterations). "Num Blocks" must be at least 2.
   - "Maximum Restarts" indicates how many times the method is restarted. A
   restart occurs when the basis has been filled to the designated capacity.
   - "Num Restart Blocks" indicates the size of the basis upon restarting.
   The default is 1 (i.e., one block); however, improved performance (with
   respect to wall-clock and number of iterations) can be seen by increasing
   this.

The cost of the algorithm is mainly in the application of the operators and
the orthogonalization of the new information into the basis. For parameters
"Num Blocks" == N and "Block Size" == B, with a problem size m, the
orthogonalization cost is from one restart to the next is approximately O(m
B^2 N^2) flops (off the top of my head). Furthermore, each orthogonalization
step (i.e., each iteration of the algorithm) requires passing through the
entire basis (potentially numerous times), so that memory effects can make
this operation much slower than the operation count would suggest.

The optimal choice for these parameters requires knowing the distribution of
the eigenvalues. It is often the case that after a restart, the iteration
will spend time reconstructing a significant portion of the subspaces that
were just discarded during the restart; this typically happens in the case
where there are a number of eigenvalues clustered around the few that are
desired by the solver (in this case, "Block Size" few). One solution is to
prevent the iteration from recomputing those components, by enlarging the
restart size ("Num Restart Blocks") to help ensure that they are retained.
This has the effect of limiting the negative effects restarting by limiting
the amount of information that is thrown away during the restart. In the
limit (as "Num Restart Blocks" grow to "Num Blocks"), it becomes equivalent
to not restarting. Of course, without restarting, there is no way to
continue the algorithm in the presence of a fixed basis size.

Without significant domain-specific insight, it can be difficult to
determine, a priori, optimal choices for these algorithmic parameters. The
paper "Dynamic Thick Restarting of the Davidson and Implicitly Restarted
Arnoldi Methods" (Stathopoulos, Saad, Wu 1998 SIAM J. Sci. Comput.)
discusses some heuristics for attempting this, focusing on dynamic choices
of the restart size. This paper also references other works which address
this problem. In particular, two works [Murray, Racine, Davidson 92] and
[Van Lenthe, Pulay 90] suggest restarting with two vectors for every
required eigenvector. This corresponds to a choice of "Num Restart Blocks"
== 2. Currently, none of the dynamic approaches proposed in the literature
are implemented in the BlockDavidsonSolMgr class in Anasazi.

I would suggest choosing "Num Restart Blocks" as some small number (2 or 3).
Try enlarging "Num Blocks", but keep in mind deterioration in orthogonality
may occur for very large values; enable OrthoDetails in the verbosity level
in your initial testing to monitor this. After you've settled on some
heuristic that you like, increase "Maximum Restarts" to a value large enough
that you converge, but not so large that you wait forever in the case that
the convergence tolerance is unreasonably low. If you believe that there are
clustered eigenvalues around the desired eigenvalues, increasing "Block
Size" or "Num Restart Blocks" to include them should help.

Others on the list with more experience on this subject are encouraged to
respond here and correct my misstatements.

Chris


On Mon, Sep 22, 2008 at 09:44, Gerry Boland <gerboland at gmail.com> wrote:

> Hello all,
> I need some advice on finding eigenvalues of an as-large-as-possible sparse
> symmetric matrix with real entries. I am using the Block-Davidson method and
> can successfully obtain the expected results.
>
> But what I'm struggling to understand are the choices of "Block Size" and
> "Block Number" - I'd like to be able to choose these at run-time if possible
> for my case. Currently my ad-hoc choices sometimes work, and sometimes the
> algorithm hasn't converged before hitting the Max Restarts limit. Is this
> purely due to my lack of understanding of the algorithm? Or are there some
> rough choices that will get the job done?
>
> And advice or recommended references on this would be very much
> appreciated!
> Thanking you in advance
> -Gerry Boland
>
> _______________________________________________
> Trilinos-Users mailing list
> Trilinos-Users at software.sandia.gov
> http://software.sandia.gov/mailman/listinfo/trilinos-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://software.sandia.gov/mailman/private/trilinos-users/attachments/20080923/9dd4c99f/attachment-0001.html