%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 }