Improvement on the northby algorithm for molecular conformation: Better solutions

Research output: Contribution to journalArticlepeer-review

58 Scopus citations


In 1987, Northby presented an efficient lattice based search and optimization procedure to compute ground states of n-atom Lennard-Jones clusters and reported putative global minima for 13≤n≤150. In this paper, we introduce simple data structures which reduce the time complexity of the Northby algorithm for lattice search from O(n5/3) per move to O(n2/3) per move for an n-atom cluster involving full Lennard-Jones potential function. If nearest neighbor potential function is used, the time complexity can be further reduced to O(log n) per move for an n-atom cluster. The lattice local minimizers with lowest potential function values are relaxed by a powerful Truncated Newton algorithm. We are able to reproduce the minima reported by Northby. The improved algorithm is so efficient that less than 3 minutes of CPU time on the Cray-XMP is required for each cluster size in the above range. We then further improve the Northby algorithm by relaxing every lattice local minimizer found in the process. This certainly requires more time. However, lower energy configurations were found with this improved algorithm for n=65, 66, 75, 76, 77 and 134. These findings also show that in some cases, the relaxation of a lattice local minimizer with a worse potential function value may lead to a local minimizer with a better potential function value.

Original languageEnglish (US)
Pages (from-to)425-440
Number of pages16
JournalJournal of Global Optimization
Issue number4
StatePublished - Jun 1994
Externally publishedYes


  • Molecular conformation
  • better solutions
  • data structures
  • improved algorithms

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics
  • Business, Management and Accounting (miscellaneous)
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Improvement on the northby algorithm for molecular conformation: Better solutions'. Together they form a unique fingerprint.

Cite this