Distance descending ordering method: an O(n) algorithm for inverting the mass matrix in simulation of macromolecules with long branches

DOI10.1016/J.JCP.2017.08.006MaRDI QIDQ1695352zbMATHOpenAlexFDO

Authors Xiankun Xu, Peiwen Li

Publication date 7 February 2018

Published in Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.10005

zbMATH Keywords

sparse matrixCholesky decompositionmass matrixmolecular dynamicsinternal coordinates\(O(n)\) time complexity

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50)

Abstract: Fixman's work in 1974 and the follow-up studies have developed a method that can factorize the inverse of mass matrix into an arithmetic combination of three sparse matrices---one of them is positive definite and need to be further factorized by using the Cholesky decomposition or similar methods. When the molecule subjected to study is of serial chain structure, this method can achieve $O(n)$ computational complexity. However, for molecules with long branches, Cholesky decomposition about the corresponding positive definite matrix will introduce massive fill-in due to its nonzero structure, which makes the calculation in scaling of $O(n^3)$. Although several methods have been used in factorizing the positive definite sparse matrices, no one could strictly guarantee for no fill-in for all molecules according to our test, and thus $O(n)$ efficiency cannot be obtained by using these traditional methods. In this paper we present a new method that can guarantee for no fill-in in doing the Cholesky decomposition, and as a result, the inverting of mass matrix will remain the $O(n)$ scaling, no matter the molecule structure has long branches or not.

Recommendations

• Comparison of two methods for solving linear equations occurring in molecular dynamics applications
• A fast recursive algorithm for molecular dynamics simulation
• scientific article; zbMATH DE number 1262862
• Finding off-diagonal entries of the inverse of a large symmetric sparse matrix
• A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances

Cites work

• scientific article; zbMATH DE number 3366440 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• An Approximate Minimum Degree Ordering Algorithm
• Computing the Minimum Fill-In is NP-Complete
• Parallel iterative methods for sparse linear systems
• The elimination form of the inverse and its application to linear programming

Describes a project that uses

Uses Software

• symrcm

This page was built for publication: Distance descending ordering method: an \(O(n)\) algorithm for inverting the mass matrix in simulation of macromolecules with long branches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1695352)