Exploiting Symmetry
A recent article by Coleman on exploiting structure for
portfolio optimization is an eyeopener for realtime
optimization. The article talks about decomposing a dense matrix into
a diagonal matrix and a linear term. The diagonal matrix can be solved
in linear time
as opposed to polynomial time
for the full dense matrix.
Symmetry can also be used in speeding up particle dynamics. Routines like
molecular and celestial dynamics propagate in time
by solving Newton’s equations of motion. If every body interacts with
every other body in the system, the interaction graph of N bodies will
be a complete graph
, ie with
edges. Simple implementations will store the interactions in the
graph’s square adjacency matrix of size N, with
entries. The use of Newton’s third law

allows us to populate just half the matrix. This results in a huge increase in speed (either for simulation or control.) I’ve created a contour plot of a symmetric random matrix with zeros along the diagonal to demonstrate the fact.

Further reductions can be made in mechanical systems with symmetry. If the set of canonical transformations on the phase space is a symmetry group, leaving the Hamiltonian invariant, then the equations of motion can be brought down to a lower dimension space of orbits of the symmetry group. Why re-calculate something that isn’t going to change?
Further, if the equations of motion are invariant under a set of transformations (either in space or time), then conservation laws are realized. This is Noether’s Theorem.
In conclusion, though disguised most times, structure and symmetry show up in problems all the time. This post was inspired by rod’s post on the fenews article. Thanks!
