Search

In this article, we focus on the communication costs of three symmetric matrix computations: i) multiplying a matrix with its transpose, known as a symmetric rank-k update (SYRK) ii) adding the result of the multiplication of a matrix with the transpose of another matrix and the transpose of that result, known as a symmetric rank-2k update (SYR2K) iii) performing matrix multiplication with a symmetric input matrix (SYMM). All three computations appear in the Level 3 Basic Linear Algebra Subroutines (BLAS) and have wide use in applications involving symmetric matrices. We establish communication lower bounds for these kernels using sequential and distributed-memory parallel computational models, and we show that our bounds are tight by presenting communication-optimal algorithms for each setting. Our lower bound proofs rely on applying a geometric inequality for symmetric computations and analytically solving constrained nonlinear optimization problems. The symmetric matrix and its corresponding computations are accessed and performed according to a triangular block partitioning scheme in the optimal algorithms., Comment: 43 pages, 6 figures. To be published in ACM Transactions on Parallel Computing

Given (orthonormal) approximations $\tilde{U}$ and $\tilde{V}$ to the left and right subspaces spanned by the leading singular vectors of a matrix $A$, we discuss methods to approximate the leading singular values of $A$ and study their accuracy. In particular, we focus our analysis on the generalized Nystr\"om approximation, as surprisingly, it is able to obtain significantly better accuracy than classical methods, namely Rayleigh-Ritz and (one-sided) projected SVD. A key idea of the analysis is to view the methods as finding the exact singular values of a perturbation of $A$. In this context, we derive a matrix perturbation result that exploits the structure of such $2\times2$ block matrix perturbation. Furthermore, we extend it to block tridiagonal matrices. We then obtain bounds on the accuracy of the extracted singular values. This leads to sharp bounds that predict well the approximation error trends and explain the difference in the behavior of these methods. Finally, we present an approach to derive an a-posteriori version of those bounds, which are more amenable to computation in practice.

It is important for official statistics production to apply ML with statistical rigor, as it presents both opportunities and challenges. Although machine learning has enjoyed rapid technological advances in recent years, its application does not possess the methodological robustness necessary to produce high quality statistical results. In order to account for all sources of error in machine learning models, the Total Machine Learning Error (TMLE) is presented as a framework analogous to the Total Survey Error Model used in survey methodology. As a means of ensuring that ML models are both internally valid as well as externally valid, the TMLE model addresses issues such as representativeness and measurement errors. There are several case studies presented, illustrating the importance of applying more rigor to the application of machine learning in official statistics., Comment: 29 pages, 4 figures, 1 table. To appear in the proceedings of the conference on Foundations and Advances of Machine Learning in Official Statistics, which was held in Wiesbaden, from 3rd to 5th April, 2024

Online platform businesses can be identified by using web-scraped texts. This is a classification problem that combines elements of natural language processing and rare event detection. Because online platforms are rare, accurately identifying them with Machine Learning algorithms is challenging. Here, we describe the development of a Machine Learning-based text classification approach that reduces the number of false positives as much as possible. It greatly reduces the bias in the estimates obtained by using calibrated probabilities and ensembles., Comment: 2 pages, 1 figure, 1 table

General relativity is highly successful in explaining a wide range of gravitational phenomena including the gravitational waves emitted by binary systems and the shadows cast by supermassive black holes. From a modern perspective the theory is not fundamental though, but constitutes the lowest order term in an effective field theory description of the gravitational force. As a consequence, the gravitational dynamics should receive corrections by higher-derivative terms. This essay discusses structural aspects associated with these corrections and summarizes their imprint on static, spherically symmetric geometries. Along these lines, we critically reassess the common practice of using local field redefinitions in order to simplify the dynamics at the danger of shifting physics effects into sectors which are beyond the approximation under consideration., Comment: 10 pages. Essay received Honorable Mention at the Gravity Research Foundation 2024 Awards for Essays on Gravitation. v2: fixed typos and updated to match published version

We study the adiabatic connection that has as weak-coupling expansion the M{\o}ller-Plesset perturbation series, generalizing to the open-shell case previous closed-shell results for the large-coupling limit. We first focus on the hydrogen atom with fractional spins, providing results along the adiabatic connection, from small to large coupling strengths. We reveal an intriguing phase diagram, and an equation for the large-coupling leading order that has closed-form solutions for specific choices of its relevant quantum numbers. We then show that the hydrogen atom results provide variational estimates for the large-coupling leading terms for the general many-electron open-shell case in terms of functionals of the Hartree-Fock {\alpha}-spin and {\beta}-spin densities., Comment: 13 pages, 4 figures (7 panels)

This paper introduces a fully algebraic two-level additive Schwarz preconditioner for general sparse large-scale matrices. The preconditioner is analyzed for symmetric positive definite (SPD) matrices. For those matrices, the coarse space is constructed based on approximating two local subspaces in each subdomain. These subspaces are obtained by approximating a number of eigenvectors corresponding to dominant eigenvalues of two judiciously posed generalized eigenvalue problems. The number of eigenvectors can be chosen to control the condition number. For general sparse matrices, the coarse space is constructed by approximating the image of a local operator that can be defined from information in the coefficient matrix. The connection between the coarse spaces for SPD and general matrices is also discussed. Numerical experiments show the great effectiveness of the proposed preconditioners on matrices arising from a wide range of applications. The set of matrices includes SPD, symmetric indefinite, nonsymmetric, and saddle-point matrices. In addition, we compare the proposed preconditioners to the state-of-the-art domain decomposition preconditioners.

We determine the corrections to the Schwarzschild geometry arising from including the Goroff- Sagnotti counterterm in the gravitational dynamics. We find that static, asymptotically flat, and spherically symmetric geometries are completely characterized by their asymptotic mass and the coupling associated with the counterterm. The latter induces distinct corrections at sixth order of the parameterized post-Newtonian expansion. The resulting spacetime geometries still exhibit an event horizon. In the parameter space accessible to numerical integration, the horizon area is smaller than its Schwarzschild counterpart, leading to an increase in the Hawking temperature. Corrections to the shadow size can be determined analytically and are used to give a first bound on the new coupling. While it is difficult to access the geometry inside of the event horizon, our analysis also provides evidence that the counterterm could resolve the curvature singularity appearing in the Schwarzschild geometry., Comment: 7 pages, 2 figures, v2: some improvements and clarifications, references added

We prove a $p$-adic version of the work by Gross and Zagier on the differences between singular moduli by proving a set of conjectures by Giampietro and Darmon, who investigated the factorisation of a rational invariant associated to a pair of CM-points on a genus zero Shimura curve, obtained as the ratio of the CM-values of $p$-adic $\Theta$-functions. As did Gross and Zagier, we give two proofs; an algebraic proof using CM-theory, and more interestingly, also an analytic proof using $p$-adic infinitesimal deformations of Hilbert Eisenstein series. Since there are no explicit formulae for its cuspidal $p$-adic deformations, we instead compute the Frobenius traces of the appropriate Galois deformation, and show their modularity via an $R = T$ theorem. This approach aims to bridge the gap between classical CM-theory and the more recent $p$-adic advances in the theory of real multiplication., Comment: 35 pages

Non-covalent interactions (NCIs) play a crucial role in biology, chemistry, material science, and everything in between. To improve pure quantum-chemical simulations of NCIs, we propose a methodology for constructing approximate correlation energies by combining an interpolation along the M{\o}ller adiabatic connection (MP AC) with a regularization and spin-scaling strategy applied to MP2 correlation energies. This combination yields $c_{\rm os}\kappa_{\rm os}$-SPL2, which exhibits superior accuracy for NCIs compared to any of the individual strategies. With the $N^4$ formal scaling, $c_{\rm os}\kappa_{\rm os}$-SPL2, is competitive or often outperforms more expensive dispersion-corrected double hybrids for NCIs.The accuracy of $c_{\rm os}\kappa_{\rm os}$-SPL2 particularly shines for anionic halogen bonded complexes, where it surpasses standard dispersion-corrected DFT by a factor of 3 to 5., Comment: 12 pages + 5 SI, 8 figures + 6 SI

We study numerically the strong-interaction limit of the exchange-correlation functional for neutral atoms and for Bohr atoms as the number of electrons increases. Using a compact representation, we analyse the second-order gradient expansion, comparing it with the one for exchange (weak interaction limit). The two gradient expansions, at strong and weak interaction, turn out to be very similar in magnitude, but with opposite signs. We find that the point-charge plus continuum model is surprisingly accurate for the gradient expansion coefficient at strong coupling, while generalized gradient approximations such as PBE and PBEsol severely underestimate it. We then use our results to analyse the Lieb-Oxford bound from the point of view of slowly-varying densities, clarifying some aspects on the bound at fixed number of electrons., Comment: 11 pages, 5 figures

Multiple Tensor-Times-Matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimensional data analysis. We establish communication lower bounds that determine how much data movement is required to perform the Multi-TTM computation in parallel. The crux of the proof relies on analytically solving a constrained, nonlinear optimization problem. We also present a parallel algorithm to perform this computation that organizes the processors into a logical grid with twice as many modes as the input tensor. We show that with correct choices of grid dimensions, the communication cost of the algorithm attains the lower bounds and is therefore communication optimal. Finally, we show that our algorithm can significantly reduce communication compared to the straightforward approach of expressing the computation as a sequence of tensor-times-matrix operations.