[Trilinos-Users] Block-Davidson usage advice needed

[Gerry Boland]

Dear Chris,
thank you for your detailed and informative reply. It's exactly what I need.

-Gerry

On 23/09/2008, Chris Baker <cgbaker at gmail.com> wrote:
>
> 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/20080924/6d75d3f2/attachment.html