Thick-Restart Block Lanczos Method for Large-Scale Shell-Model Calculations

Noritaka Shimizu; Takahiro Mizusaki; Yutaka Utsuno; Yusuke Tsunoda

Source-linked AI summary

Thick-Restart Block Lanczos Method for Large-Scale Shell-Model Calculations

Noritaka Shimizu, Takahiro Mizusaki, Yutaka Utsuno, Yusuke Tsunoda

arXiv:1902.02064v1Feb 6, 2019nucl-thphysics.comp-ph

TL;DR

Large-scale shell-model calculations increasingly require many eigenvalues, particularly for highly excited states with dense spectra. The paper introduces a thick-restart block Lanczos eigensolver in KSHELL, combining block processing with restart control. It reports reduced iterations and elapsed time relative to conventional Lanczos calculations while supporting massively parallel computation.

Problem
Highly excited-state studies require O(10^2)-O(10^3) eigenstates, beyond the small numbers of low-lying states conventionally targeted.
Source: §I · p. 1
Method
The paper combines block Lanczos and thick restart in KSHELL, using block operations and restricted Lanczos-vector storage for large-scale calculations.
Source: §I · p. 1, D. Thick-restart block Lanczos method · p. 5, §V · p. 9
Results
The method reduces iterations and elapsed time in KSHELL calculations, including the reported 48Cr and 112Sn examples, while improving handling of many eigenvalues.
Source: B. Performance of the block algorithm · p. 8, §V · p. 9
Takeaways & Limitations
The thick-restart block Lanczos method supports efficient computation of highly excited shell-model states and near-degenerate eigenvalues.
Source: C. Block Lanczos method · p. 5, §V · p. 9

Abstract

from arXiv · show

We propose a thick-restart block Lanczos method, which is an extension of the thick-restart Lanczos method with the block algorithm, as an eigensolver of the large-scale shell-model calculations. This method has two advantages over the conventional Lanczos method: the precise computations of the near-degenerate eigenvalues, and the efficient computations for obtaining a large number of eigenvalues. These features are quite advantageous to compute highly excited states where the eigenvalue density is rather high. A shell-model code, named KSHELL, equipped with this method was developed for massively parallel computations, and it enables us to reveal nuclear statistical properties which are intensively investigated by recent experimental facilities. We describe the algorithm and performance of the KSHELL code and demonstrate that the present method outperforms the conventional Lanczos method.

I. INTRODUCTION

Large-scale shell-model calculations increasingly target highly excited states, requiring many eigenvalues where conventional methods face growing computational demands. The paper combines block and thick-restart Lanczos techniques for this setting.

I. INTRODUCTION

Traditional Lanczos and thick-restart Lanczos methods are effective mainly for obtaining a small number of low-lying eigenvalues.Source: §I · p. 1
Recent experiments motivate shell-model calculations of highly excited states and statistical properties such as γ-ray strength functions and level densities.These studies require approximately O(10^2)-O(10^3) eigenstates.Source: §I · p. 1
The proposed block approach can reduce matrix-element generation costs because multiple matrix-vector products are performed together.This is especially relevant when KSHELL generates matrix elements on the fly.Source: §I · pp. 1–2
The paper presents the method within KSHELL, a shell-model code designed for massively parallel computation.The paper also discusses the code’s algorithm, performance, and organization.Source: §I · pp. 1–2

II. LSSM WITH M-SCHEME BASIS STATES

The M-scheme represents shell-model wave functions as combinations of Slater determinants and exploits Hamiltonian symmetries to reduce the eigenvalue problem. Its dimensionality has grown substantially with computational capabilities.

II. LSSM WITH M-SCHEME BASIS STATES

M-scheme basis states are Slater determinants describing occupations of active single-particle states, with configurations conveniently stored as bit representations.Source: §II · p. 2
The shell-model wave function is a linear combination of M-scheme basis states, with coefficients obtained by solving the Hamiltonian eigenvalue problem.Source: §II · p. 2
The Hamiltonian contains one-body and two-body interactions, with the latter represented by Two-Body Matrix Elements.Source: §II · p. 2
Rotational and parity symmetries make the many-body Hamiltonian block diagonal, so calculations treat blocks specified by M and π.Source: §II · p. 2
The tractable M-scheme dimension increases exponentially with publication year and recently reaches 10^11.The rightmost reported point is a KSHELL calculation for 32Mg using sd- and pf-shells with particle-hole excitations up to 8ℏω.Source: §II · pp. 2–3

III. LANCZOS ALGORITHMS

The paper proposes the thick-restart block Lanczos method by combining block Lanczos with thick restart for large-scale shell-model calculations.

III. LANCZOS ALGORITHMS

The proposed method combines block Lanczos with thick restart to efficiently compute many eigenstates in large-scale shell-model calculations.The paper reviews naive and thick-restart Lanczos methods before describing the block variants.Source: §III · p. 3

A. Lanczos method

The Lanczos method approximates low-lying eigenvalues of a huge sparse symmetric Hamiltonian through a Krylov subspace and iteratively refined Ritz values. Reorthogonalization preserves numerical orthogonality but can become a major cost as the iteration count grows.

A. Lanczos method

Lanczos approximates Hamiltonian eigenvalues by diagonalizing a tridiagonal matrix associated with the Krylov subspace.The Krylov subspace contains successive matrix-vector products H^jv_1.Source: A. Lanczos method · p. 3
The method uses a three-term recurrence involving the current and two preceding Lanczos vectors.Source: A. Lanczos method · p. 3
Ritz values approach the exact eigenvalues of the original matrix as the iteration index increases.Source: A. Lanczos method · p. 3
Matrix-vector products exploit Hamiltonian sparsity because the matrix is accessed without storing or processing zero elements.Source: A. Lanczos method · p. 3
Reorthogonalization preserves numerical orthogonality but costs O(k^2D_M) operations and O(kD_M) memory, creating a bottleneck for large k.Source: A. Lanczos method · p. 3

B. Thick-restart Lanczos method

The thick-restart Lanczos method compresses the accumulated Lanczos subspace into a smaller set of low-eigenvalue vectors before continuing iterations. This limits vector storage and reorthogonalization costs while retaining the targeted Ritz information.

Restart procedure

The method restarts Lanczos iterations by compressing the full Lanczos-vector set into vectors associated with the lowest eigenvalues.The compressed subspace is formed from the lowest ls eigenvectors of the projected problem before restart.Source: B. Thick-restart Lanczos method · p. 4

Algorithm

The algorithm constructs Lanczos vectors through matrix-vector products, orthogonalization, projected-matrix diagonalization, and a restart step.Algorithm 2 repeats the standard Lanczos loop and then constructs a new projected matrix and vector set for restart.Source: B. Thick-restart Lanczos method · p. 4

Restart construction

The retained Ritz values and eigenvectors determine the restarted vectors and the corresponding projected-matrix structure.The restart retains ls eigenvalues and uses the associated projected eigenvectors to reconstruct the new basis.Source: B. Thick-restart Lanczos method · p. 4

Orthogonality

Reorthogonalization with all previous vectors is required immediately after the restart, even though the ordinary three-term recurrence otherwise applies.The algorithm performs this full reorthogonalization after restarting before resuming the iteration sequence.Source: B. Thick-restart Lanczos method · p. 4

C. Block Lanczos method

The block Lanczos method groups multiple vectors into matrix blocks and builds a block Krylov subspace. It is designed to handle clustered or degenerate eigenvalues and to reduce iteration-related costs when many states are sought.

Block construction

The method bundles p initial vectors into a DM × p block and forms the block Krylov subspace {V1, HV1, H^2V1, ..., H^(m−1)V1}.The block size p is the number of initial vectors grouped in V1.Source: C. Block Lanczos method · p. 4

Convergence

As m increases, Ritz values from the block Krylov subspace are expected to converge faster than those from the ordinary Krylov subspace.The convergence claim concerns the Ritz values of the block-generated subspace.Source: C. Block Lanczos method · p. 4

Algorithm

Each iteration multiplies the Hamiltonian by a block, orthogonalizes the result, applies QR decomposition, and updates a symmetric block-tridiagonal projected matrix.The projected matrix is assembled from p × p α and β blocks.Source: C. Block Lanczos method · pp. 4–5

Advantages

The block method can accurately obtain degenerate eigenvalues up to the block size and is useful for highly excited states with increasing level density.The simple Lanczos method is described as more efficient when only a small number of states is required.Source: C. Block Lanczos method · p. 5
Matrix-matrix products are generally more efficient than matrix-vector products, while the block method can reduce iterations and elapsed time when many eigenvalues are required.In KSHELL, fewer iterations can also reduce the frequency of on-the-fly matrix-element generation.Source: C. Block Lanczos method · pp. 4–5

D. Thick-restart block Lanczos method

The thick-restart block Lanczos method combines block iteration with thick restarting to retain block-method advantages while controlling the enlarged Lanczos basis. Restarting keeps the basis below a prescribed upper limit and reduces reorthogonalization costs.

Motivation

The proposed method combines block Lanczos with thick restart to address the larger Lanczos-vector count and associated reorthogonalization cost.The method extends thick-restart Lanczos by using block vectors and is presented as the paper’s combined algorithm.Source: D. Thick-restart block Lanczos method · pp. 5–6

Algorithm

The algorithm iterates block matrix-vector products, updates projected blocks, diagonalizes the projected matrix, orthogonalizes new blocks, and periodically restarts.Restart construction occurs after the block iteration and resets the retained-vector count.Source: D. Thick-restart block Lanczos method · p. 5

Restart control

The restart is performed so that the number of Lanczos vectors does not exceed the upper limit lm.After restart, the projected matrix and vectors are reconstructed using the same procedure as in the thick-restart method.Source: D. Thick-restart block Lanczos method · p. 5

Restart construction

The restarted projected matrix uses E(ls), whose diagonal entries are the Ritz values retained immediately before restarting.The retained values are (e1, e2, ..., els).Source: D. Thick-restart block Lanczos method · p. 5

Computational cost

Thick restarting restricts the number of Lanczos vectors and reduces the reorthogonalization cost that tends to increase in the block algorithm.The retained post-restart vectors are constructed from the pre-restart projected eigenvectors.Source: D. Thick-restart block Lanczos method · pp. 5–6

IV. PERFORMANCE OF THE LANCZOS METHODS

The paper compares four eigensolver variants by examining their convergence properties and practical performance. The methods are simple Lanczos, thick-restart Lanczos, block Lanczos, and thick-restart block Lanczos.

Comparison scope

Four Lanczos-based eigensolvers are compared: simple Lanczos, thick-restart Lanczos, block Lanczos, and thick-restart block Lanczos.Convergence properties are discussed in one subsection and practical performance is compared in another.Source: §IV · p. 6

A. Convergence of the Lanczos method and its variants

For 48Cr, higher eigenvalues converge much more slowly with simple Lanczos, while block and thick-restart variants reduce iteration or storage costs with restart-dependent trade-offs.

The benchmark uses 48Cr in the pf-shell model space with the GXPF1A interaction and an M-scheme dimension of 1,963,461.Source: A. Convergence of the Lanczos method… · p. 6
The lowest eigenvalue converges at iteration 44, whereas the 32nd reaches convergence at iteration 466 under a 10^-6 MeV Ritz-value criterion.Source: A. Convergence of the Lanczos method… · p. 6
The simple-Lanczos calculation requires all 467 Lanczos vectors for reorthogonalization and, if needed, eigenvector extraction.Source: A. Convergence of the Lanczos method… · p. 6
Block Lanczos with p = 2, 4, or 8 reaches convergence in substantially fewer iterations than simple Lanczos, with iterations slightly exceeding 1/p of the simple method.The larger number of stored vectors is reported to be offset by faster matrix-block products.Source: A. Convergence of the Lanczos method… · pp. 6–7
Thick restart reduces stored vectors and reorthogonalization cost, but overly frequent restarts slow convergence; p = 8 improves when lm increases from 100 to 200.Source: A. Convergence of the Lanczos method… · p. 7

B. Performance of the block algorithm

The block algorithm trades higher matrix-block product costs for fewer iterations, with performance depending on block size, restart settings, and initialization. Benchmarks show substantial speedups for 48Cr and 112Sn, especially when many eigenvalues are requested.

In KSHELL, block processing generates matrix elements once for a bundle of vectors instead of at every individual matrix-vector product.This design targets the on-the-fly matrix-element generation cost.Source: B. Performance of the block algorithm · p. 7
The 48Cr convergence count falls from 466 iterations at p = 1 to 53 at p = 32, almost 1/9 as large.Source: B. Performance of the block algorithm · p. 8
For 48Cr, p = 8 gives the shortest total elapsed time because it balances iteration reduction against matrix-block product cost.Matrix-block products account for roughly 80% of total elapsed time.Source: B. Performance of the block algorithm · p. 8
Computing 128 lowest eigenvalues with lm = 800 is fastest at p = 16 and achieves 3.5 times speedup over thick-restart Lanczos.Source: B. Performance of the block algorithm · p. 8
For 112Sn, matrix-block product time depends weakly on block size because on-the-fly generation dominates, while iterations reach 47 at p = 32.Source: B. Performance of the block algorithm · pp. 8–9
Using particle-hole truncated-approximation initial vectors reduces the 112Sn computation time to 672 seconds versus 6,077 seconds without the block algorithm.Source: B. Performance of the block algorithm · p. 9

V. SUMMARY

The paper introduces the thick-restart block Lanczos method and the KSHELL code for large-scale shell-model calculations. KSHELL uses M-scheme representations, on-the-fly matrix-element generation, and massively parallel computation to reduce computational costs.

V. SUMMARY

The thick-restart block Lanczos method combines block Lanczos with thick restart for large-scale shell-model eigensolvers.The block approach targets clustered or near-degenerate eigenvalues and many low-lying eigenvalues, while thick restart limits the Lanczos vectors requiring reorthogonalization.Source: §V · p. 9
The method reduces elapsed time for large-scale calculations by lowering iteration counts and reorthogonalization costs.The block algorithm reduces the frequency of on-the-fly matrix-element generation, while thick restart restricts the number of Lanczos vectors.Source: §V · p. 9
KSHELL is an M-scheme shell-model code developed for massively parallel computation and highly excited-state calculations.The code divides M-scheme basis states into partitions classified by occupation numbers and proton angular-momentum projections.Source: §V · p. 9, Appendix A · pp. 9–10
The Hamiltonian matrix is huge and sparse, making explicit storage impractical for large shell-model spaces.For 56Ni in the pf shell, the M-scheme dimension is 1,087,455,228 and explicit storage would require 14.4 TB.Source: Appendix B · pp. 10–11, Appendix A · p. 10
KSHELL avoids explicit Hamiltonian storage by generating matrix elements on the fly during matrix-vector products.M-scheme Slater determinants are represented as binary numbers, and two-body interactions are applied using bitwise operations and basis-index searches.Source: Appendix B · p. 11, §1 · p. 11

1. Parallel computation of a matrix-vector product

KSHELL parallelizes matrix-vector products by partitioning the Hamiltonian and balancing expensive diagonal work across processes. Its communication layout is suited to torus-connected systems, while thick restart limits reorthogonalization overhead.

1. Parallel computation of a matrix-vector product

54,104 non-zero elements occupy 13.2% of the 20Ne Hamiltonian matrix, whose 640-dimensional space is divided into 162×162 partitions.Partitions are used as parallel-computation units, and empty partition pairs are excluded in advance.Source: §1 · p. 11, Figure 10 · p. 12
6,030,189 non-zero elements give the 24Mg Hamiltonian a sparsity of 0.7%.The block-diagonal structure is denser than the non-diagonal part, so diagonal partitions require especially careful load balancing.Source: §1 · pp. 11–12, Figure 11 · p. 12
The blocked assignment distributes partition work to balance diagonal costs and minimize Lanczos-vector communication.The design uses partition-based computation, equal distribution of expensive diagonal partitions, and reduced network transfers.Source: §1 · p. 12
16D/Np bytes of communication are required per matrix-vector product, decreasing as the number of parallel nodes increases.This two-dimensional communication topology matches the torus interconnection network of the K computer.Source: §1 · pp. 12–13

2. Parallel computation of reorthogonalization

39 iterations mark the point where HDD reorthogonalization exceeds matrix-vector-product time in the 56Ni benchmark.Keeping Lanczos vectors in memory reduces reorthogonalization time by two orders of magnitude relative to a matrix-vector product, but requires sufficient memory.Source: §2 · p. 13