Assignment Collection & Simplifications¶

AssignmentCollection¶

class AssignmentCollection(main_assignments, subexpressions=None, simplification_hints=None, subexpression_symbol_generator=None)¶

A collection of equations with subexpression definitions, also represented as assignments, that are used in the main equations. AssignmentCollection can be passed to simplification methods. These simplification methods can change the subexpressions, but the number and left hand side of the main equations themselves is not altered. Additionally a dictionary of simplification hints is stored, which are set by the functions that create assignment collections to transport information to the simplification system.

Parameters

main_assignments (Union[List[Assignment], Dict[Expr, Expr]]) – List of assignments. Main assignments are characterised, that the right hand side of each assignment is a field access. Thus the generated equations write on arrays.
subexpressions (Union[List[Assignment], Dict[Expr, Expr], None]) – List of assignments defining subexpressions used in main equations
simplification_hints (Optional[Dict[str, Any]]) – Dict that is used to annotate the assignment collection with hints that are used by the simplification system. See documentation of the simplification rules for potentially required hints and their meaning.
subexpression_symbol_generator (Optional[Iterator[Symbol]]) – Generator for new symbols that are used when new subexpressions are added used to get new symbols that are unique for this AssignmentCollection

add_simplification_hint(key, value)¶

Adds an entry to the simplification_hints dictionary and checks that is does not exist yet.

Return type: None

add_subexpression(rhs, lhs=None, topological_sort=True)¶

Adds a subexpression to current collection.

Parameters

rhs (Expr) – right hand side of new subexpression
lhs (Optional[Symbol]) – optional left hand side of new subexpression. If None a new unique symbol is generated.
topological_sort – sort the subexpressions topologically after insertion, to make sure that definition of a symbol comes before its usage. If False, subexpression is appended.

Return type

Symbol

Returns

left hand side symbol (which could have been generated)

topological_sort(sort_subexpressions=True, sort_main_assignments=True)¶

Sorts subexpressions and/or main_equations topologically to make sure symbol usage comes after definition.

Return type: None

property all_assignments: List[sympy.codegen.ast.Assignment]¶

Subexpression and main equations as a single list.

Return type: List[Assignment]

property rhs_symbols: Set[sympy.core.symbol.Symbol]¶

All symbols used in the assignment collection, which occur on the rhs of any assignment.

Return type: Set[Symbol]

property free_symbols: Set[sympy.core.symbol.Symbol]¶

All symbols used in the assignment collection, which do not occur as left hand sides in any assignment.

Return type: Set[Symbol]

property bound_symbols: Set[sympy.core.symbol.Symbol]¶

All symbols which occur on the left hand side of a main assignment or a subexpression.

Return type: Set[Symbol]

property rhs_fields¶: All fields accessed in the assignment collection, which do not occur as left hand sides in any assignment.

property free_fields¶: All fields accessed in the assignment collection, which do not occur as left hand sides in any assignment.

property bound_fields¶: All field accessed on the left hand side of a main assignment or a subexpression.

property defined_symbols: Set[sympy.core.symbol.Symbol]¶

All symbols which occur as left-hand-sides of one of the main equations

Return type: Set[Symbol]

property operation_count¶: See count_operations()

dependent_symbols(symbols)¶

Returns all symbols that depend on one of the passed symbols.

A symbol ‘a’ depends on a symbol ‘b’, if there is an assignment ‘a <- some_expression(b)’ i.e. when ‘b’ is required to compute ‘a’.

Return type: Set[Symbol]

lambdify(symbols, fixed_symbols=None, module=None)¶

Returns a python function to evaluate this equation collection.

Parameters

symbols (Sequence[Symbol]) – symbol(s) which are the parameter for the created function
fixed_symbols (Optional[Dict[Symbol, Any]]) – dictionary with substitutions, that are applied before sympy’s lambdify
module – same as sympy.lambdify parameter. Defines which module to use e.g. ‘numpy’

Examples

>>> a, b, c, d = sp.symbols("a b c d")
>>> ac = AssignmentCollection([Assignment(c, a + b), Assignment(d, a**2 + b)],
...                           subexpressions=[Assignment(b, a + b / 2)])
>>> python_function = ac.lambdify([a], fixed_symbols={b: 2})
>>> python_function(4)
{c: 6, d: 18}

copy(main_assignments=None, subexpressions=None)¶

Returns a copy with optionally replaced main_assignments and/or subexpressions.

Return type: AssignmentCollection

new_with_substitutions(substitutions, add_substitutions_as_subexpressions=False, substitute_on_lhs=True, sort_topologically=True)¶

Returns new object, where terms are substituted according to the passed substitution dict.

Parameters

substitutions (Dict) – dict that is passed to sympy subs, substitutions are done main assignments and subexpressions
add_substitutions_as_subexpressions (bool) – if True, the substitutions are added as assignments to subexpressions
substitute_on_lhs (bool) – if False, the substitutions are done only on the right hand side of assignments
sort_topologically (bool) – if subexpressions are added as substitutions and this parameters is true, the subexpressions are sorted topologically after insertion

Return type

AssignmentCollection

Returns

New AssignmentCollection where substitutions have been applied, self is not altered.

new_merged(other)¶

Returns a new collection which contains self and other. Subexpressions are renamed if they clash.

Return type: AssignmentCollection

new_filtered(symbols_to_extract)¶

Extracts equations that have symbols_to_extract as left hand side, together with necessary subexpressions.

Return type: AssignmentCollection
Returns: new AssignmentCollection, self is not altered

new_without_unused_subexpressions()¶

Returns new collection that only contains subexpressions required to compute the main assignments.

Return type: AssignmentCollection

new_with_inserted_subexpression(symbol)¶

Eliminates the subexpression with the given symbol on its left hand side, by substituting it everywhere.

Return type: AssignmentCollection

new_without_subexpressions(subexpressions_to_keep=None)¶

Returns a new collection where all subexpressions have been inserted.

Return type: AssignmentCollection

SimplificationStrategy¶

class SimplificationStrategy¶

A simplification strategy is an ordered collection of simplification rules.

Each simplification is a function taking an assignment collection, and returning a new simplified assignment collection. The strategy can nicely print intermediate simplification stages and results to Jupyter notebooks.

add(rule)¶

Adds the given simplification rule to the end of the collection.

Parameters: rule (Callable[[AssignmentCollection], AssignmentCollection]) – function that rewrites/simplifies an assignment collection
Return type: None

apply(assignment_collection)¶

Runs all rules on the given assignment collection.

Return type: AssignmentCollection

create_simplification_report(assignment_collection)¶

Creates a report to be displayed as HTML in a Jupyter notebook.

The simplification report contains the number of operations at each simplification stage together with the run-time the simplification took.

Return type: Any

show_intermediate_results(assignment_collection, symbols=None)¶

Shows the assignment collection after the application of each rule as HTML report for Jupyter notebook.

Parameters

assignment_collection (AssignmentCollection) – the collection to apply the rules to
symbols (Optional[Sequence[Symbol]]) – if not None, only the assignments are shown that have one of these symbols as left hand side

Return type

Any

Simplifications¶

sort_assignments_topologically(assignments)¶

Sorts assignments in topological order, such that symbols used on rhs occur first on a lhs

Return type: List[Union[Assignment, Node]]

sympy_cse(ac, **kwargs)¶

Searches for common subexpressions inside the assignment collection.

Searches is done in both the existing subexpressions as well as the assignments themselves. It uses the sympy subexpression detection to do this. Return a new assignment collection with the additional subexpressions found

sympy_cse_on_assignment_list(assignments)¶

Extracts common subexpressions from a list of assignments.

Return type: List[Assignment]

subexpression_substitution_in_existing_subexpressions(ac)¶: Goes through the subexpressions list and replaces the term in the following subexpressions.

subexpression_substitution_in_main_assignments(ac)¶: Replaces already existing subexpressions in the equations of the assignment_collection.

add_subexpressions_for_constants(ac)¶

Extracts constant factors to subexpressions in the given assignment collection.

SymPy will exclude common factors from a sum only if they are symbols. This simplification can be applied to exclude common numeric constants from multiple terms of a sum. As a consequence, the number of multiplications is reduced and in some cases, more common subexpressions can be found.

add_subexpressions_for_divisions(ac)¶

Introduces subexpressions for all divisions which have no constant in the denominator.

For example \(\frac{1}{x}\) is replaced while \(\frac{1}{3}\) is not replaced.

add_subexpressions_for_sums(ac)¶: Introduces subexpressions for all sums - i.e. splits addends into subexpressions.

add_subexpressions_for_field_reads(ac, subexpressions=True, main_assignments=True)¶

Substitutes field accesses on rhs of assignments with subexpressions

Can change semantics of the update rule (which is the goal of this transformation) This is useful if a field should be update in place - all values are loaded before into subexpression variables, then the new values are computed and written to the same field in-place.

transform_rhs(assignment_list, transformation, *args, **kwargs)¶: Applies a transformation function on the rhs of each element of the passed assignment list If the list also contains other object, like AST nodes, these are ignored. Additional parameters are passed to the transformation function

apply_to_all_assignments(operation)¶: Applies a given operation to all equations in collection.

apply_on_all_subexpressions(operation)¶: Applies the given operation on all subexpressions of the AC.

Subexpression insertion¶

The subexpression insertions have the goal to insert subexpressions which will not reduce the number of FLOPs. For example a constant value kept as subexpression will lead to a new variable in the code which will occupy a register slot. On the other side a single variable could just be inserted in all assignments.

insert_subexpressions(ac, selection_callback, skip=None)¶

Removes a number of subexpressions from an assignment collection by inserting their right-hand side wherever they occur.

Parameters

selection_callback (-) – Function that is called to qualify subexpressions for insertion. Should return True for any subexpression that is to be inserted, and False otherwise.
skip (-) – Set of symbols (left-hand sides of subexpressions) that should be ignored even if qualified by the callback.

insert_aliases(ac, **kwargs)¶: Inserts subexpressions that are aliases of other symbols, i.e. their right-hand side is only another symbol.

insert_zeros(ac, **kwargs)¶: Inserts subexpressions whose right-hand side is zero.

insert_constants(ac, **kwargs)¶: Inserts subexpressions whose right-hand side is constant, i.e. contains no symbols.

insert_symbol_times_minus_one(ac, **kwargs)¶: Inserts subexpressions whose right-hand side is just a negation of another symbol.

insert_constant_multiples(ac, **kwargs)¶: Inserts subexpressions whose right-hand side is a constant multiplied with another symbol.

insert_constant_additions(ac, **kwargs)¶: Inserts subexpressions whose right-hand side is a sum of a constant and another symbol.

insert_squares(ac, **kwargs)¶: Inserts subexpressions whose right-hand side is another symbol squared.