Low-rank update algorithms for statistical physics applications
P. Nukala, G. Alvarez, and E. D'azevedo. Abstract Book of the XXIII IUPAP International Conference on Statistical Physics, Genova, Italy, (9-13 July 2007)
Abstract
Many of statistical physics applications involve problems in which a basic linear algebra sub-problem is repetitively solved during each of the simulation steps. For example, investigation of material fracture of disordered systems using discrete lattice systems involves repetitively solving a new, large system of equations each time a lattice bond fails. Failure of a bond is equivalent to a low-rank downdating of the original system of equations. Similarly, Monte Carlo (MC) simulation of a strongly correlated electron or spin-fermion systems involves repetitive computation of eigenvalues of a new Hamiltonian matrix each time a local change is accepted. Each of these local changes in MC simulation is equivalent to a low-rank updating of the Hamiltonian matrix. Thus, an important feature of such problems is that successive matrices differ by a low-rank update/downdate.
\par
Traditional algorithms employ repetitive computation techniques wherein the linear algebra sub-problem is repetitively solved during each of the simulation steps. This poses a significant computational challenge even for modern supercomputers since a large number of MC steps are required to solve the problem. Furthermore, the linear algebra sub-problem involved in each of these MC steps does not scale well and the computational complexity of these sub-problems increases as $O(N^3)$, where $N$ is the size of the matrix. On the other hand, since successive matrices differ by a low-rank update, an updating scheme of some kind is likely to be more efficient than employing a repetitive computational technique during each of the MC steps.
\par
This work presents algorithms based on low-rank updates, namely, a multiple-rank sparse Cholesky algorithm for efficiently computing the successive solutions of linear systems, and an algorithm for recomputing eigenvalues when successive Hamiltonian matrices differ by a low-rank update.
%0 Book Section
%1 statphys23_1023
%A Nukala, P.K.V.V.
%A Alvarez, G.
%A D'azevedo, E.
%B Abstract Book of the XXIII IUPAP International Conference on Statistical Physics
%C Genova, Italy
%D 2007
%E Pietronero, Luciano
%E Loreto, Vittorio
%E Zapperi, Stefano
%K fracture low-rank spin-fermion statphys23 system topic-11 updates
%T Low-rank update algorithms for statistical physics applications
%U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=1023
%X Many of statistical physics applications involve problems in which a basic linear algebra sub-problem is repetitively solved during each of the simulation steps. For example, investigation of material fracture of disordered systems using discrete lattice systems involves repetitively solving a new, large system of equations each time a lattice bond fails. Failure of a bond is equivalent to a low-rank downdating of the original system of equations. Similarly, Monte Carlo (MC) simulation of a strongly correlated electron or spin-fermion systems involves repetitive computation of eigenvalues of a new Hamiltonian matrix each time a local change is accepted. Each of these local changes in MC simulation is equivalent to a low-rank updating of the Hamiltonian matrix. Thus, an important feature of such problems is that successive matrices differ by a low-rank update/downdate.
\par
Traditional algorithms employ repetitive computation techniques wherein the linear algebra sub-problem is repetitively solved during each of the simulation steps. This poses a significant computational challenge even for modern supercomputers since a large number of MC steps are required to solve the problem. Furthermore, the linear algebra sub-problem involved in each of these MC steps does not scale well and the computational complexity of these sub-problems increases as $O(N^3)$, where $N$ is the size of the matrix. On the other hand, since successive matrices differ by a low-rank update, an updating scheme of some kind is likely to be more efficient than employing a repetitive computational technique during each of the MC steps.
\par
This work presents algorithms based on low-rank updates, namely, a multiple-rank sparse Cholesky algorithm for efficiently computing the successive solutions of linear systems, and an algorithm for recomputing eigenvalues when successive Hamiltonian matrices differ by a low-rank update.
@incollection{statphys23_1023,
abstract = {Many of statistical physics applications involve problems in which a basic linear algebra sub-problem is repetitively solved during each of the simulation steps. For example, investigation of material fracture of disordered systems using discrete lattice systems involves repetitively solving a new, large system of equations each time a lattice bond fails. Failure of a bond is equivalent to a low-rank downdating of the original system of equations. Similarly, Monte Carlo (MC) simulation of a strongly correlated electron or spin-fermion systems involves repetitive computation of eigenvalues of a new Hamiltonian matrix each time a local change is accepted. Each of these local changes in MC simulation is equivalent to a low-rank updating of the Hamiltonian matrix. Thus, an important feature of such problems is that successive matrices differ by a low-rank update/downdate.
\par
Traditional algorithms employ repetitive computation techniques wherein the linear algebra sub-problem is repetitively solved during each of the simulation steps. This poses a significant computational challenge even for modern supercomputers since a large number of MC steps are required to solve the problem. Furthermore, the linear algebra sub-problem involved in each of these MC steps does not scale well and the computational complexity of these sub-problems increases as $O(N^3)$, where $N$ is the size of the matrix. On the other hand, since successive matrices differ by a low-rank update, an updating scheme of some kind is likely to be more efficient than employing a repetitive computational technique during each of the MC steps.
\par
This work presents algorithms based on low-rank updates, namely, a multiple-rank sparse Cholesky algorithm for efficiently computing the successive solutions of linear systems, and an algorithm for recomputing eigenvalues when successive Hamiltonian matrices differ by a low-rank update.},
added-at = {2007-06-20T10:16:09.000+0200},
address = {Genova, Italy},
author = {Nukala, P.K.V.V. and Alvarez, G. and D'azevedo, E.},
biburl = {https://www.bibsonomy.org/bibtex/25850207052cee0d467b4cb581d1c4c6b/statphys23},
booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics},
editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano},
interhash = {695c521ec96472058b80906d01b1d962},
intrahash = {5850207052cee0d467b4cb581d1c4c6b},
keywords = {fracture low-rank spin-fermion statphys23 system topic-11 updates},
month = {9-13 July},
timestamp = {2007-06-20T10:16:37.000+0200},
title = {Low-rank update algorithms for statistical physics applications},
url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=1023},
year = 2007
}