We propose a new algorithm for calculation of vibrational spectra of molecules using tensor train decomposition. Under the assumption that eigenfunctions lie on a low-parametric manifold of low-rank tensors we suggest using well-known iterative methods that utilize matrix inversion (locally optimal block preconditioned conjugate gradient method, inverse iteration) and solve corresponding linear systems inexactly along this manifold. As an application, we accurately compute vibrational spectra (84 states) of acetonitrile molecule CH3CN on a laptop in one hour using only 100 MB of memory to represent all computed eigenfunctions.
The PINVIT iteration can explicitly utilize a preconditioner. The construction of preconditioners in tensor formats for eigenvalue problems was considered in @cite_30 @cite_18 @cite_0 @cite_42 . The approach for a general operator @cite_42 uses Newton-Schulz iteration in order to find a good preconditioner. However, due to high amount of matrix multiplications, this approach becomes time-consuming. In order to construct a preconditioner one can use approximate inverse matrix or approximate solution of linear systems. See @cite_22 @cite_7 @cite_28 @cite_32 for solvers in tensor formats.
@cite_30 @cite_18 @cite_22 @cite_7 @cite_28 @cite_42 @cite_32 @cite_0
2098102734 2042199958 2051142108 2025033760 2246353276 2073656615 2287294391 950823788
The paper introduces the sweeping preconditioner, which is highly efficient for iterative solutions of the variable-coefficient Helmholtz equation including very-high-frequency problems. The first central idea of this novel approach is to construct an approximate factorization of the discretized Helmholtz equation by sweeping the domain layer by layer, starting from an absorbing layer or boundary condition. Given this specific order of factorization, the second central idea is to represent the intermediate matrices in the hierarchical matrix framework. In two dimensions, both the construction and the application of the preconditioners are of linear complexity. The generalized minimal residual method (GMRES) solver with the resulting preconditioner converges in an amazingly small number of iterations, which is essentially independent of the number of unknowns. This approach is also extended to the three-dimensional case with some success. Numerical results are provided in both two and three dimensions to demonstrate the efficiency of this new approach. An iterative solution method, in the form of a preconditioner for a Krylov subspace method, is presented for the Helmholtz equation. The preconditioner is based on a Helmholtz-type differential operator with a complex term. A multigrid iteration is used for approximately inverting the preconditioner. The choice of multigrid components for the corresponding preconditioning matrix with a complex diagonal is validated with Fourier analysis. Multigrid analysis results are verified by numerical experiments. High wavenumber Helmholtz problems in heterogeneous media are solved indicating the performance of the preconditioner. We describe new algorithms of the locally optimal block preconditioned conjugate gradient (LOBPCG) method for symmetric eigenvalue problems, based on a local optimization of a three-term recurrence, and suggest several other new methods. To be able to compare numerically different methods in the class, with different preconditioners, we propose a common system of model tests, using random preconditioners and initial guesses. As the "ideal" control algorithm, we advocate the standard preconditioned conjugate gradient method for finding an eigenvector as an element of the null-space of the corresponding homogeneous system of linear equations under the assumption that the eigenvalue is known. We recommend that every new preconditioned eigensolver be compared with this "ideal" algorithm on our model test problems in terms of the speed of convergence, costs of every iteration, and memory requirements. We provide such comparison for our LOBPCG method. Numerical results establish that our algorithm is practically as efficient as the ideal'' algorithm when the same preconditioner is used in both methods. We also show numerically that the LOBPCG method provides approximations to first eigenpairs of about the same quality as those by the much more expensive global optimization method on the same generalized block Krylov subspace. We propose a new version of block Davidson's method as a generalization of the LOBPCG method. Finally, direct numerical comparisons with the Jacobi--Davidson method show that our method is more robust and converges almost two times faster. An algebraic multilevel (ML) preconditioner is presented for the Helmholtz equation in heterogeneous media. It is based on a multilevel incomplete @math factorization and preserves the inherent (complex) symmetry of the Helmholtz equation. The ML preconditioner incorporates two key components for efficiency and numerical stability: symmetric maximum weight matchings and an inverse-based pivoting strategy. The former increases the block-diagonal dominance of the system, whereas the latter controls @math for numerical stability. When applied recursively, their combined effect yields an algebraic coarsening strategy, similar to algebraic multigrid methods, even for highly indefinite matrices. The ML preconditioner is combined with a Krylov subspace method and applied as a “black-box” solver to a series of challenging two- and three-dimensional test problems, mainly from geophysical seismic imaging. The numerical results demonstrate the robustness and efficiency of the ML preconditioner, even at higher frequency regimes. An efficient power flow solution is highly important for power system analyses. Traditionally, LU decomposition-based direct method is dominant in solving linear systems in the power flow analysis. However, with the increasing scale and complexity, direct methods may suffer scalability issues, especially under parallel implementation. Therefore, iterative methods such as Conjugate Gradient (CG) are gaining more attention for their scalability and feasibility for parallelisation. To efficiently apply an iterative solver like CG, a preconditioner is usually required. A polynomial-based Chebyshev preconditioner is discussed in this work. An essential parameter in Chebyshev preconditioning is the maximum eigenvalue of the linear system. However, direct calculation of the eigenvalues is too time-consuming to be practical. Therefore, this work proposes a method to estimate the largest eigenvalue to save the time spent on eigenvalue calculation. Thus, Chebyshev preconditioning will be practical to use in power system analyses. This work first proves that the eigenvalues of power system applications range within (0, 2] after a normalisation step, then demonstrates the eigenvalue estimation accuracy, and finally presents the performance improvement. The test shows an average 98.92 runtime saving for the Chebyshev preconditioner, and a 40.99 runtime saving for precondition and iterative solving process. In the present paper we analyze a class of tensor-structured preconditioners for the multidimensional second-order elliptic operators in ℝ d , d≥2. For equations in a bounded domain, the construction is based on the rank-R tensor-product approximation of the elliptic resolvent ℬ R ≈(ℒ−λ I)−1, where ℒ is the sum of univariate elliptic operators. We prove the explicit estimate on the tensor rank R that ensures the spectral equivalence. For equations in an unbounded domain, one can utilize the tensor-structured approximation of Green’s kernel for the shifted Laplacian in ℝ d , which is well developed in the case of nonoscillatory potentials. For the oscillating kernels e −i κ‖x‖ ‖x‖, x∈ℝ d , κ∈ℝ+, we give constructive proof of the rank-O(κ) separable approximation. This leads to the tensor representation for the discretized 3D Helmholtz kernel on an n×n×n grid that requires only O(κ |log e|2 n) reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost O(n 2), even in the case κ=O(n). The computational and storage complexity of kernel machines presents the primary barrier to their scaling to large, modern, datasets. A common way to tackle the scalability issue is to use the conjugate gradient algorithm, which relieves the constraints on both storage (the kernel matrix need not be stored) and computation (both stochastic gradients and parallelization can be used). Even so, conjugate gradient is not without its own issues: the conditioning of kernel matrices is often such that conjugate gradients will have poor convergence in practice. Preconditioning is a common approach to alleviating this issue. Here we propose preconditioned conjugate gradients for kernel machines, and develop a broad range of preconditioners particularly useful for kernel matrices. We describe a scalable approach to both solving kernel machines and learning their hyperparameters. We show this approach is exact in the limit of iterations and outperforms state-of-the-art approximations for a given computational budget. Using a finite element method to solve the Helmholtz equation leads to a sparse system of equations which in three dimensions is too large to solve directly. It is also non-Hermitian and highly indefinite and consequently difficult to solve iteratively. The approach taken in this paper is to precondition this linear system with a new preconditioner and then solve it iteratively using a Krylov subspace method. Numerical analysis shows the preconditioner to be effective on a simple 1D test problem, and results are presented showing considerable convergence acceleration for a number of different Krylov methods for more complex problems in 2D, as well as for the more general problem of harmonic disturbances to a non-stagnant steady flow.