When it comes to eliminating subexpressions, they say:
"This is to be expected; ultimately, the algorithm is a simple greedy algorithm, which often doesn’t have the best track record with this sort of optimization problem. Trying to minimize the number of floating point operations required for the polynomial calculation is also likely an NP-hard problem, so any algorithm that actually solved this problem would be even slower than the one we came up with. "
It depends on what you mean -
1. Finding syntatically common subexpressions is linear or n log n depending how you do it
2. Eliminating the maximum possible existing value-equivalent subexpressions is polynomial.
3. Finding the smallest possible set of operations or instructions to evaluate a set of expressions is provably NP-complete (as a decision problem).
The difference between #2 and #3 is #2 is restricted to results already computed somewhere in the program (even as a subexpression), as well as canonical reordering of expression trees to expose as many of these as possible. #3 is not limited in this way. In all cases, you have to restrict to herbrand equivalence if you want it to not run into undecidability issues, at least as trying to prove things go. In practice, all compilers go beyond herbrand equivalence in specific cases to deal with common value identities (IE x+0 = x).
The Molecular Theory is a theoretical and computational framework for the study of soft matter (polymers, surfactants, gels, biological membranes, etc). For example, this theory has been used to study polymer self-assembly, biological nanopores and nanoparticles modified by polymers. The objective of this framework is to find the density and chemical state of all molecules (polymers, solvent molecules and/or ions) in each position of the system. To achieve this, the system’s free energy is written down as an approximated functional of these unknown functions. Analytically minimizing the free energy functional provides analytical expressions for the densities and chemical states. These expressions are discretized following a finite differences scheme which results in a coupled non linear equation system. In order to find a solution for this system we have to find a solution vector X such as F(x) = 0 (where F is the set of coupled non linear equations). The solution to this problem is obtained by employing a variant of Newton’s method. The evaluation of F(x) in each iteration of the method is the most taxing part of the whole program (performance wise) because it requires the multiplication and addition of very large sparse matrices. As of today, the storage and computation of these sparse matrixes operations is done employing an in-house compressed format which doesn’t store the null elements, but the real efficiency of the employed routines hasn’t been evaluated for possible optimizations. Additionally, the code employs the MPI standard for parallelizing the computations, but doesn’t implement optimizations for massively parallel architectures.
---
eventually I'll try to port it to GPU, if that is even possible or ideal.