Chebyshev filter diagonalization is well established in quantum chemistry and quantum physics to compute bulks of eigenvalues of large sparse matrices. Choosing a block vector implementation, we investigate optimization opportunities on the new class of high-performance compute devices featuring both high-bandwidth and low-bandwidth memory. We focus on the transparent access to the full address space supported by both architectures under consideration: Intel Xeon Phi “Knights Landing” and Nvidia “Pascal” “Volta.” After a thorough performance analysis of the single-device implementations using the roofline model we propose two optimizations: (1) Subspace blocking is applied for improved performance and data access efficiency. We also show that it allows transparently handling problems much larger than the high-bandwidth memory without significant performance penalties. (2) Pipelining of communication and computation phases of successive subspaces is implemented to hide communication costs without extra memory traffic. As an application scenario we perform filter diagonalization studies for topological quantum matter. Performance numbers on up to 2048 nodes of the Oakforest-PACS and Piz Daint supercomputers are presented, achieving beyond 500 Tflop s for computing (10^2 ) inner eigenvalues of sparse matrices of dimension (4 10^9 ).
From a computational perspective, the evaluation of Chebyshev polynomials is a simple series of vector operations and sparse matrix-vector multiplications (SpMV). It allows for kernel fusion to increase the computational intensity @cite_21 . Global communication can be avoided or limited to a single invocation for the full-degree polynomial. In the above application scenarios the polynomial is usually evaluated for multiple vectors and the algorithm can be reformulated to use blocks of vectors. This further increases the computational intensity and pushes the corresponding sparse matrix-multiple-vector multiplication (SpMMV) towards regular data access @cite_21 . We emphasize that the benefits of SpMMV have been known for a long time @cite_4 but have only recently gained renewed interest (see, e.g., @cite_26 @cite_9 @cite_13 ).
@cite_26 @cite_4 @cite_9 @cite_21 @cite_13
2024211806 2141454789 2083676493 1993855803
Chebyshev polynomial approximations are an efficient and numerically stable way to calculate properties of the very large Hamiltonians important in computational condensed matter physics. The present paper derives an optimal kernel polynomial which enforces positivity of density of states and spectral estimates, achieves the best energy resolution, and preserves normalization. This kernel polynomial method (KPM) is demonstrated for electronic structure and dynamic magnetic susceptibility calculations. For tight binding Hamiltonians of Si, we show how to achieve high precision and rapid convergence of the cohesive energy and vacancy formation energy by careful attention to the order of approximation. For disordered XXZ-magnets, we show that the KPM provides a simpler and more reliable procedure for calculating spectral functions than Lanczos recursion methods. Polynomial approximations to Fermi projection operators are also proposed. We consider the problem of recovering polynomials that are sparse with respect to the basis of Legendre polynomials from a small number of random samples. In particular, we show that a Legendre s-sparse polynomial of maximal degree N can be recovered from [email protected]?slog^4(N) random samples that are chosen independently according to the Chebyshev probability measure [email protected](x)[email protected]^-^1(1-x^2)^-^1^ ^2dx. As an efficient recovery method, @?"1-minimization can be used. We establish these results by verifying the restricted isometry property of a preconditioned random Legendre matrix. We then extend these results to a large class of orthogonal polynomial systems, including the Jacobi polynomials, of which the Legendre polynomials are a special case. Finally, we transpose these results into the setting of approximate recovery for functions in certain infinite-dimensional function spaces. Abstract : The present paper deals with the problem of computing a few of the eigenvalues with largest (or smallest) real parts, of a large sparse nonsymmetric matrix. We present a general acceleration technique based on Chebyshev polynomials and discuss its practical application to Arnoldi's method and the subspace iteration method. The resulting algorithms are compared with the classical ones in a few experiments which exhibit a sharp superiority of the Arnoldi-Chebyshev approach. In this paper, we attempt to approximate and index a d- dimensional (d ≥ 1) spatio-temporal trajectory with a low order continuous polynomial. There are many possible ways to choose the polynomial, including (continuous)Fourier transforms, splines, non-linear regressino, etc. Some of these possiblities have indeed been studied beofre. We hypothesize that one of the best possibilities is the polynomial that minimizes the maximum deviation from the true value, which is called the minimax polynomial. Minimax approximation is particularly meaningful for indexing because in a branch-and-bound search (i.e., for finding nearest neighbours), the smaller the maximum deviation, the more pruning opportunities there exist. However, in general, among all the polynomials of the same degree, the optimal minimax polynomial is very hard to compute. However, it has been shown thta the Chebyshev approximation is almost identical to the optimal minimax polynomial, and is easy to compute [16]. Thus, in this paper, we explore how to use the Chebyshev polynomials as a basis for approximating and indexing d-dimenstional trajectories.The key analytic result of this paper is the Lower Bounding Lemma. that is, we show that the Euclidean distance between two d-dimensional trajectories is lower bounded by the weighted Euclidean distance between the two vectors of Chebyshev coefficients. this lemma is not trivial to show, and it ensures that indexing with Chebyshev cofficients aedmits no false negatives. To complement that analystic result, we conducted comprehensive experimental evaluation with real and generated 1-dimensional to 4-dimensional data sets. We compared the proposed schem with the Adaptive Piecewise Constant Approximation (APCA) scheme. Our preliminary results indicate that in all situations we tested, Chebyshev indexing dominates APCA in pruning power, I O and CPU costs.