Memory-optimal evaluation of expression trees involving large objects

The need to evaluate expression trees involving large objects arises in scientific computing applications such as electronic structure calculations. Often, the tree node objects are so large that only a subset of them can fit into memory at a time. This paper addresses the problem of finding an evaluation order of the nodes in a given expression tree that uses the least amount of memory. We present an algorithm that finds an optimal evaluation order in Θ(nlog2n) time for an n-node expression tree and prove its correctness. We demonstrate the utility of our algorithm using representative equations from quantum chemistry.