{"id":{"repo_id":"rice","oai_identifier":"oai:repository.rice.edu:1911/19185"},"canonical_url":"https://search.dev.ndltd.org/etd/rice/oai:repository.rice.edu:1911/19185","repository":{"repo_id":"rice","name":"Rice University","base_url":"https://repository.rice.edu/server/oai/request"},"display":{"title":"Conjugate gradient density matrix search: A linear scaling alternative to diagonalization","abstract":"Advances in the computation of the Coulomb, exchange, and correlation contributions to Gaussian-based Hartree-Fock and density functional theory Hamiltonians have demonstrated near-linear scaling with molecular size for these steps. These advances leave the ${\\cal O}(N\\sp3)$ diagonalization bottleneck as the rate determining step for very large systems. In this work, a conjugate gradient density matrix search (CG-DMS) method has been successfully extended and computationally implemented for use with first principles calculations. A Cholesky decomposition of the overlap matrix and its inverse, which can be formed in near linear time for sparse systems, is used to transform to and back from an orthonormal basis. Linear scaling of CPU time for the density matrix search and crossover of CPU time with diagonalization is demonstrated for polyglycine chains containing up to 493 atoms and water clusters up to 900 atoms.","abstract_html":"Advances in the computation of the Coulomb, exchange, and correlation contributions to Gaussian-based Hartree-Fock and density functional theory Hamiltonians have demonstrated near-linear scaling with molecular size for these steps. These advances leave the ${\\cal O}(N\\sp3)$ diagonalization bottleneck as the rate determining step for very large systems. In this work, a conjugate gradient density matrix search (CG-DMS) method has been successfully extended and computationally implemented for use with first principles calculations. A Cholesky decomposition of the overlap matrix and its inverse, which can be formed in near linear time for sparse systems, is used to transform to and back from an orthonormal basis. Linear scaling of CPU time for the density matrix search and crossover of CPU time with diagonalization is demonstrated for polyglycine chains containing up to 493 atoms and water clusters up to 900 atoms.","abstract_has_math":true,"creators":["Millam, John Mark"],"institution":"Rice University","degree_name":"Doctor of Philosophy","degree_level":"Doctoral","degree_discipline":"Natural Sciences","degree_department":null,"school":null,"contributors":[],"advisors":["Scuseria, Gustavo E."],"committee_chairs":[],"committee_members":[],"year":1997,"date_issued":"1997","date_published":"1997","updated_at":"2026-07-24T04:10:24Z","subjects":["Physical chemistry"],"languages":["eng"],"rights":["Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1911/19185","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Scuseria, Gustavo E."]},{"key":"dc:creator","label":"Author","values":["Millam, John Mark"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-06-04T08:37:42Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-06-04T08:37:42Z"]},{"key":"dc:date.issued","label":"Date","values":["1997"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Natural Sciences"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Rice University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Physical chemistry"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1911/19185"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Advances in the computation of the Coulomb, exchange, and correlation contributions to Gaussian-based Hartree-Fock and density functional theory Hamiltonians have demonstrated near-linear scaling with molecular size for these steps. These advances leave the ${\\cal O}(N\\sp3)$ diagonalization bottleneck as the rate determining step for very large systems. In this work, a conjugate gradient density matrix search (CG-DMS) method has been successfully extended and computationally implemented for use with first principles calculations. A Cholesky decomposition of the overlap matrix and its inverse, which can be formed in near linear time for sparse systems, is used to transform to and back from an orthonormal basis. Linear scaling of CPU time for the density matrix search and crossover of CPU time with diagonalization is demonstrated for polyglycine chains containing up to 493 atoms and water clusters up to 900 atoms."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Conjugate gradient density matrix search: A linear scaling alternative to diagonalization"]}]}],"canonical_facts":{"dc:contributor.advisor":["Scuseria, Gustavo E."],"dc:creator":["Millam, John Mark"],"dc:date.accessioned":["2009-06-04T08:37:42Z"],"dc:date.available":["2009-06-04T08:37:42Z"],"dc:date.issued":["1997"],"dc:description.abstract":["Advances in the computation of the Coulomb, exchange, and correlation contributions to Gaussian-based Hartree-Fock and density functional theory Hamiltonians have demonstrated near-linear scaling with molecular size for these steps. These advances leave the ${\\cal O}(N\\sp3)$ diagonalization bottleneck as the rate determining step for very large systems. In this work, a conjugate gradient density matrix search (CG-DMS) method has been successfully extended and computationally implemented for use with first principles calculations. A Cholesky decomposition of the overlap matrix and its inverse, which can be formed in near linear time for sparse systems, is used to transform to and back from an orthonormal basis. Linear scaling of CPU time for the density matrix search and crossover of CPU time with diagonalization is demonstrated for polyglycine chains containing up to 493 atoms and water clusters up to 900 atoms."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["https://hdl.handle.net/1911/19185"],"dc:language.iso":["eng"],"dc:rights":["Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder."],"dc:subject":["Physical chemistry"],"dc:title":["Conjugate gradient density matrix search: A linear scaling alternative to diagonalization"],"dc:type":["Thesis"],"thesis:degree_discipline":["Natural Sciences"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Rice University"]},"updated_at":"2026-07-24T04:10:24Z"}