Google Summer of Code Week 6: Unification and Tensors Continued

Posted on July 7, 2019 by Ankit Pandey

See the previous post for Week 5.

This week I’ve made some progress on matching and tensors, though I haven’t filed any pull requests.

Unification

I have a working implementation of rewriting non-commutative expressions using SymPy’s unify. It works by generating a ReplaceOptim object that applies the rewriting rules to any term it’s called with. Here’s how we specify the rewriting rules:

Here, the combination of matcher and variables specifies that we’re looking for any expression of the form X1YX^{-1}Y , where both XX and YY can be any compound matrix expression. The inclusion of n in variables imposes the additional restriction that the matrix expression matched by XX must be square (i.e. n×nn \times n ) while the expression matched by YY must be a vector (i.e. n×1n \times 1 ). goal specifies what the matched expression should be replaced with, where X and Y serve as stand-ins for the matched terms.

After specifying our goals, we can construct the object and apply the replacement to some expressions:

The first term was replaced since the dimensions of A and x agreed with what was specified in matcher, while the second expression was left untouched since B is not a vector.

While the matcher does work, I haven’t filed a pull request because of some problems which don’t seem like they could be easily addressed:

  • I had to give add the suffix _matcher to the variable names to avoid variable capture, since SymPy symbols are considered equal if they have the same name. unify does not support Dummy symbols as variables.
  • Some compound expressions are not matched. I’ve narrowed this down to the way the variables are being passed to unify, since they need to be converted to symbols. It seems like this conversion sometimes causes expressions to no longer be unifiable.
  • Unification doesn’t seem to work for a mixture of commutative and non-commutative expressions. I’m not sure if this is a problem with unify itself or the way that I’m using it, since the only test of unify in the SymPy codebase involving matrix expressions is on matrix multiplication.

As I mentioned in my last blog post, SymPy already supports this sort of pattern matching through Wild, though it currently does not support expressions involving matrices. Before trying to address these issues, I think it would be worthwhile to look into extending the functionality of Wild as an alternative.

Tensors

I’ve made some progress in low-level code generation of matrix expressions. I tried seeing if instances of classes in the array_utils module could be converted to SymPy’s AST representation before being passed off to the code generators. This doesn’t seem possible at the moment, since the AST has a number of limitations (such as not supporting variables in for loop ranges). The IndexedBase printer already has some of the functionality that I’m trying to implement, so I’ve settled on extending the printer to support arbitrary contractions. This same functionality can probably be reused for the array_utils printers. The implementation will hopefully be straightforward.

Next steps

My goal for this week is to have a pull request for the tensor code generation ready, along with a plan for what to do with matching.