ffc.uflacs.analysis package

Submodules

ffc.uflacs.analysis.balancing module

Algorithms for the representation phase of the form compilation.

class ffc.uflacs.analysis.balancing.BalanceModifiers

Bases: ufl.corealg.multifunction.MultiFunction

cell_avg(expr, *ops)

expr(expr, *ops)

Trigger error for types with missing handlers.

facet_avg(expr, *ops)

grad(expr, *ops)

negative_restricted(expr, *ops)

positive_restricted(expr, *ops)

reference_grad(expr, *ops)

reference_value(expr, *ops)

terminal(expr)

ffc.uflacs.analysis.balancing.balance_modified_terminal(expr)

ffc.uflacs.analysis.balancing.balance_modifiers(expr)

ffc.uflacs.analysis.crsarray module

Compressed row storage ‘matrix’ (actually just a non-rectangular 2d array).

class ffc.uflacs.analysis.crsarray.CRSArray(row_capacity, element_capacity, dtype)

Bases: object

An array of variable length dense arrays.

Stored efficiently with simple compressed row storage. This CRS array variant doesn’t have a sparsity pattern, as each row is simply a dense vector.

Values are stored in one flat array ‘data[]’, and ‘row_offsets[i]’ contains the index to the first element on row i for 0<=i<=num_rows. There is no column index.

classmethod from_rows(rows, num_rows, num_elements, dtype)

Construct a CRSArray from a list of row element lists.

num_elements

push_row(elements)

ffc.uflacs.analysis.crsarray.sufficient_int(maxval)

ffc.uflacs.analysis.dependencies module

Tools for analysing dependencies within expression graphs.

ffc.uflacs.analysis.dependencies.compute_dependencies(e2i, V, ignore_terminal_modifiers=True)

ffc.uflacs.analysis.dependencies.mark_active(dependencies, targets)

Return an array marking the recursive dependencies of targets.

Input: - dependencies - CRSArray of ints, a mapping from a symbol to the symbols of its dependencies. - targets - Sequence of symbols to mark the dependencies of.

Output: - active - Truth value for each symbol. - num_used - Number of true values in active array.

ffc.uflacs.analysis.dependencies.mark_image(inverse_dependencies, sources)

Return an array marking the set of symbols dependent on the sources.

Input: - dependencies - CRSArray of ints, a mapping from a symbol to the symbols of its dependencies. - sources - Sequence of symbols to mark the dependants of.

Output: - image - Truth value for each symbol. - num_used - Number of true values in active array.

ffc.uflacs.analysis.expr_shapes module

Tools for computing various shapes of ufl expressions.

The total shape is the regular shape tuple plus the index shape tuple. The index shape tuple is the tuple of index dimensions of the free indices of the expression, sorted by the count of the free indices.

The total shape of a tensor valued expression A and A[*indices(len(A.ufl_shape))] is therefore the same.

ffc.uflacs.analysis.expr_shapes.compute_all_shapes(v)

Compute the tensor-, index-, and total shape of an expr.

Returns (shape, size, index_shape, index_size, total_shape, total_size).

ffc.uflacs.analysis.expr_shapes.compute_index_shape(v)

Compute the ‘index shape’ of v.

ffc.uflacs.analysis.expr_shapes.total_shape(v)

Compute the total shape of an expr.

ffc.uflacs.analysis.factorization module

Algorithms for factorizing argument dependent monomials.

class ffc.uflacs.analysis.factorization.Factors

Bases: object

add(expr)

ffc.uflacs.analysis.factorization.add_to_fv(expr, FV, e2fi)

Add expression expr to factor vector FV and expr->FVindex mapping e2fi.

ffc.uflacs.analysis.factorization.build_argument_dependencies(dependencies, arg_indices)

Preliminary algorithm: build list of argument vertex indices each vertex (indirectly) depends on.

ffc.uflacs.analysis.factorization.build_argument_indices(V)

Build ordered list of indices to modified arguments.

ffc.uflacs.analysis.factorization.compute_argument_factorization(SV, SV_deps, SV_targets, rank)

Factorizes a scalar expression graph w.r.t. scalar Argument components.

The result is a triplet (AV, FV, IM):

• The scalar argument component subgraph:

  AV[ai] = v

  with the property

  SV[arg_indices] == AV[:]

• An expression graph vertex list with all non-argument factors:

  FV[fi] = f

  with the property that none of the expressions depend on Arguments.

• A dict representation of the final integrand of rank r:

  IM = { (ai1_1, …, ai1_r): fi1, (ai2_1, …, ai2_r): fi2, }

  This mapping represents the factorization of SV[-1] w.r.t. Arguments s.t.:

  SV[-1] := sum(FV[fik] * product(AV[ai] for ai in aik) for aik, fik in IM.items())

  where := means equivalence in the mathematical sense, of course in a different technical representation.

ffc.uflacs.analysis.factorization.handle_conditional(v, si, deps, SV_factors, FV, sv2fv, e2fi)

ffc.uflacs.analysis.factorization.handle_division(v, si, deps, SV_factors, FV, sv2fv, e2fi)

ffc.uflacs.analysis.factorization.handle_operator(v, si, deps, SV_factors, FV, sv2fv, e2fi)

ffc.uflacs.analysis.factorization.handle_product(v, si, deps, SV_factors, FV, sv2fv, e2fi)

ffc.uflacs.analysis.factorization.handle_sum(v, si, deps, SV_factors, FV, sv2fv, e2fi)

ffc.uflacs.analysis.factorization.rebuild_scalar_graph_from_factorization(AV, FV, IM)

ffc.uflacs.analysis.graph module

Linearized data structure for the computational graph.

class ffc.uflacs.analysis.graph.Graph2

Bases: object

ffc.uflacs.analysis.graph.build_graph(expressions, DEBUG=False)

ffc.uflacs.analysis.graph_rebuild module

Rebuilding UFL expressions from linearized representation of computational graph.

class ffc.uflacs.analysis.graph_rebuild.ReconstructScalarSubexpressions

Bases: ufl.corealg.multifunction.MultiFunction

abs(o, ops)

atan_2(o, ops)

bessel_function(o, ops)

component_tensor(o, *args, **kwargs)

condition(o, ops)

conditional(o, ops)

division(o, ops)

expr(o, *args, **kwargs)

Trigger error for types with missing handlers.

expr_list(o, *args, **kwargs)

expr_mapping(o, *args, **kwargs)

index_sum(o, ops)

label(o, *args, **kwargs)

list_tensor(o, *args, **kwargs)

math_function(o, ops)

max_value(o, ops)

min_value(o, ops)

multi_index(o, *args, **kwargs)

power(o, ops)

product(o, ops)

scalar_nary(o, ops)

sum(o, ops)

terminal(o)

transposed(o, *args, **kwargs)

unexpected(o, *args, **kwargs)

utility_type(o, *args, **kwargs)

variable(o, *args, **kwargs)

ffc.uflacs.analysis.graph_rebuild.rebuild_expression_from_graph(G)

This is currently only used by tests.

ffc.uflacs.analysis.graph_rebuild.rebuild_with_scalar_subexpressions(G, targets=None)

Build a new expression2index mapping where each subexpression is scalar valued.

Input: - G.e2i - G.V - G.V_symbols - G.total_unique_symbols

Output: - NV - Array with reverse mapping from index to expression - nvs - Tuple of ne2i indices corresponding to the last vertex of G.V

Old output now no longer returned but possible to restore if needed: - ne2i - Mapping from scalar subexpressions to a contiguous unique index - W - Array with reconstructed scalar subexpressions for each original symbol

ffc.uflacs.analysis.graph_ssa module

Algorithms for working with computational graphs.

ffc.uflacs.analysis.graph_ssa.allocate_registers(active, partitions, targets, scores, max_registers, score_threshold)

FIXME: Cover with tests.

TODO: Allow reuse of registers, reducing memory usage.

TODO: Probably want to sort within partitions.

ffc.uflacs.analysis.graph_ssa.compute_cache_scores(V, active, dependencies, inverse_dependencies, partitions, cache_score_policy=<function default_cache_score_policy>)

FIXME: Cover with tests.

TODO: Experiment with heuristics later when we have functional code generation.

ffc.uflacs.analysis.graph_ssa.compute_dependency_count(dependencies)

FIXME: Test

ffc.uflacs.analysis.graph_ssa.default_cache_score_policy(vtype, ndeps, ninvdeps, partition)

ffc.uflacs.analysis.graph_ssa.default_partition_seed(expr, rank)

Partition 0: Piecewise constant on each cell (including Real and DG0 coefficients) Partition 1: Depends on x Partition 2: Depends on x and coefficients Partitions [3,3+rank): depend on argument with count partition-3

ffc.uflacs.analysis.graph_ssa.invert_dependencies(dependencies, depcount)

FIXME: Test

ffc.uflacs.analysis.graph_ssa.mark_partitions(V, active, dependencies, rank, partition_seed=<function default_partition_seed>, partition_combiner=<built-in function max>)

FIXME: Cover this with tests.

Input: - V - Array of expressions. - active - Boolish array. - dependencies - CRSArray with V dependencies. - partition_seed - Policy for determining the partition of a terminalish. - partition_combiner - Policy for determinging the partition of an operator.

Output: - partitions - Array of partition int ids.

ffc.uflacs.analysis.graph_symbols module

Assigning symbols to computational graph nodes.

ffc.uflacs.analysis.graph_symbols.build_graph_symbols(V, e2i, DEBUG)

Tabulate scalar value numbering of all nodes in a a list based representation of an expression graph.

Returns: V_shapes - CRSArray of the total shapes of nodes in V. V_symbols - CRSArray of symbols (value numbers) of each component of each node in V. total_unique_symbols - The number of symbol values assigned to unique scalar components of the nodes in V.

ffc.uflacs.analysis.graph_symbols.build_node_shapes(V)

Build total shapes for each node in list representation of expression graph.

V is an array of ufl expressions, possibly nonscalar and with free indices.

Returning a CRSArray where row i is the total shape of V[i].

ffc.uflacs.analysis.graph_symbols.build_node_sizes(V_shapes)

Compute all the products of a sequence of shapes.

ffc.uflacs.analysis.graph_symbols.build_node_symbols(V, e2i, V_shapes, V_sizes)

Tabulate scalar value numbering of all nodes in a a list based representation of an expression graph.

Returns: V_symbols - CRSArray of symbols (value numbers) of each component of each node in V. total_unique_symbols - The number of symbol values assigned to unique scalar components of the nodes in V.

ffc.uflacs.analysis.graph_vertices module

Algorithms for working with graphs.

ffc.uflacs.analysis.graph_vertices.build_array_from_counts(e2i)

ffc.uflacs.analysis.graph_vertices.build_graph_vertices(expressions)

ffc.uflacs.analysis.graph_vertices.build_node_counts(expressions)

ffc.uflacs.analysis.graph_vertices.build_scalar_graph_vertices(expressions)

ffc.uflacs.analysis.graph_vertices.build_scalar_node_counts(expressions)

ffc.uflacs.analysis.graph_vertices.count_nodes_with_unique_post_traversal(expr, e2i=None, skip_terminal_modifiers=False)

Yields o for each node o in expr, child before parent. Never visits a node twice.

ffc.uflacs.analysis.indexing module

Algorithms for working with multiindices.

ffc.uflacs.analysis.indexing.map_component_tensor_arg_components(tensor)

Build integer list mapping between flattended components of tensor and its underlying indexed subexpression.

ffc.uflacs.analysis.indexing.map_indexed_arg_components(indexed)

Build integer list mapping between flattended components of indexed expression and its underlying tensor-valued subexpression.

ffc.uflacs.analysis.modified_terminals module

Definitions of ‘modified terminals’, a core concept in uflacs.

class ffc.uflacs.analysis.modified_terminals.ModifiedTerminal(expr, terminal, reference_value, base_shape, base_symmetry, component, flat_component, global_derivatives, local_derivatives, averaged, restriction)

Bases: object

A modified terminal expression is an object of a Terminal subtype, wrapped in terminal modifier types.

The variables of this class are:

expr - The original UFL expression terminal - the underlying Terminal object

global_derivatives - tuple of ints, each meaning derivative in that global direction local_derivatives - tuple of ints, each meaning derivative in that local direction reference_value - bool, whether this is represented in reference frame averaged - None, ‘facet’ or ‘cell’ restriction - None, ‘+’ or ‘-‘

component - tuple of ints, the global component of the Terminal flat_component - single int, flattened local component of the Terminal, considering symmetry

Possibly other component model: - global_component - reference_component - flat_component

argument_ordering_key()

Return a key for deterministic sorting of argument vertex indices based on the properties of the modified terminal. Used in factorization but moved here for closeness with ModifiedTerminal attributes.

as_tuple()

Return a tuple with hashable values that uniquely identifies this modified terminal.

Some of the derived variables can be omitted here as long as they are fully determined from the variables that are included here.

ffc.uflacs.analysis.modified_terminals.analyse_modified_terminal(expr)

Analyse a so-called ‘modified terminal’ expression.

Return its properties in more compact form as a ModifiedTerminal object.

A modified terminal expression is an object of a Terminal subtype, wrapped in terminal modifier types.

The wrapper types can include 0-* Grad or ReferenceGrad objects, and 0-1 ReferenceValue, 0-1 Restricted, 0-1 Indexed, and 0-1 FacetAvg or CellAvg objects.

ffc.uflacs.analysis.modified_terminals.is_modified_terminal(v)

Check if v is a terminal or a terminal wrapped in terminal modifier types.

ffc.uflacs.analysis.modified_terminals.strip_modified_terminal(v)

Extract core Terminal from a modified terminal or return None.

ffc.uflacs.analysis.valuenumbering module

Algorithms for value numbering within computational graphs.

class ffc.uflacs.analysis.valuenumbering.ValueNumberer(e2i, V_sizes, V_symbols)

Bases: ufl.corealg.multifunction.MultiFunction

An algorithm to map the scalar components of an expression node to unique value numbers, with fallthrough for types that can be mapped to the value numbers of their operands.

cell_avg(v, i)

Modifiers: terminal - the underlying Terminal object global_derivatives - tuple of ints, each meaning derivative in that global direction local_derivatives - tuple of ints, each meaning derivative in that local direction reference_value - bool, whether this is represented in reference frame averaged - None, ‘facet’ or ‘cell’ restriction - None, ‘+’ or ‘-‘ component - tuple of ints, the global component of the Terminal flat_component - single int, flattened local component of the Terminal, considering symmetry

component_tensor(A, i)

expr(v, i)

Create new symbols for expressions that represent new values.

facet_avg(v, i)

Modifiers: terminal - the underlying Terminal object global_derivatives - tuple of ints, each meaning derivative in that global direction local_derivatives - tuple of ints, each meaning derivative in that local direction reference_value - bool, whether this is represented in reference frame averaged - None, ‘facet’ or ‘cell’ restriction - None, ‘+’ or ‘-‘ component - tuple of ints, the global component of the Terminal flat_component - single int, flattened local component of the Terminal, considering symmetry

form_argument(v, i)

Create new symbols for expressions that represent new values.

get_node_symbols(expr)

grad(v, i)

Modifiers: terminal - the underlying Terminal object global_derivatives - tuple of ints, each meaning derivative in that global direction local_derivatives - tuple of ints, each meaning derivative in that local direction reference_value - bool, whether this is represented in reference frame averaged - None, ‘facet’ or ‘cell’ restriction - None, ‘+’ or ‘-‘ component - tuple of ints, the global component of the Terminal flat_component - single int, flattened local component of the Terminal, considering symmetry

indexed(Aii, i)

list_tensor(v, i)

new_symbol()

Generator for new symbols with a running counter.

new_symbols(n)

Generator for new symbols with a running counter.

reference_grad(v, i)

Modifiers: terminal - the underlying Terminal object global_derivatives - tuple of ints, each meaning derivative in that global direction local_derivatives - tuple of ints, each meaning derivative in that local direction reference_value - bool, whether this is represented in reference frame averaged - None, ‘facet’ or ‘cell’ restriction - None, ‘+’ or ‘-‘ component - tuple of ints, the global component of the Terminal flat_component - single int, flattened local component of the Terminal, considering symmetry

reference_value(v, i)

Modifiers: terminal - the underlying Terminal object global_derivatives - tuple of ints, each meaning derivative in that global direction local_derivatives - tuple of ints, each meaning derivative in that local direction reference_value - bool, whether this is represented in reference frame averaged - None, ‘facet’ or ‘cell’ restriction - None, ‘+’ or ‘-‘ component - tuple of ints, the global component of the Terminal flat_component - single int, flattened local component of the Terminal, considering symmetry

restricted(v, i)

Modifiers: terminal - the underlying Terminal object global_derivatives - tuple of ints, each meaning derivative in that global direction local_derivatives - tuple of ints, each meaning derivative in that local direction reference_value - bool, whether this is represented in reference frame averaged - None, ‘facet’ or ‘cell’ restriction - None, ‘+’ or ‘-‘ component - tuple of ints, the global component of the Terminal flat_component - single int, flattened local component of the Terminal, considering symmetry

variable(v, i)

Direct reuse of all symbols.

Module contents

Algorithms for the analysis phase of the form compilation.