polynomials.h File Reference

Polynomial representation and manipulation. More...

#include "sdfg/symbolic/symbolic.h"

Go to the source code of this file.

Classes
struct	sdfg::symbolic::AffineDecomposition
	Result of affine decomposition of an expression w.r.t. More...

Namespaces
namespace	sdfg
namespace	sdfg::symbolic

Typedefs
typedef SymEngine::RCP< const SymEngine::MExprPoly >	sdfg::symbolic::Polynomial
	Type representing a SymEngine polynomial expression.
typedef std::unordered_map< Symbol, Expression, SymEngine::RCPBasicHash, SymEngine::RCPBasicKeyEq >	sdfg::symbolic::AffineCoeffs
	Map from symbols to their coefficients in an affine expression.

Functions
Polynomial	sdfg::symbolic::polynomial (const Expression expr, SymbolVec &symbols)
	Converts an Expression to a Polynomial.
AffineCoeffs	sdfg::symbolic::affine_coefficients (Polynomial poly)
	Converts a Polynomial of degree 1 to coefficient map.
bool	sdfg::symbolic::is_integer_affine (const Expression &expr)
	Whether expr is affine in all of its symbols with integer coefficients, e.g.
Expression	sdfg::symbolic::affine_inverse (AffineCoeffs coeffs, Symbol symbol)
	Computes the inverse function for an affine expression.
AffineDecomposition	sdfg::symbolic::affine_decomposition (const Expression &expr, const Symbol &symbol)
	Decomposes an expression into affine form w.r.t.
Expression	sdfg::symbolic::solve_affine_bound (const Expression &expr, const Symbol &symbol, const Expression &bound_value, bool is_lower_bound)
	Solves for a symbol's bound given an inequality constraint.
std::pair< Expression, Expression >	sdfg::symbolic::polynomial_div (const Expression &dividend, const Expression &divisor)
	Performs polynomial division.

Detailed Description

Polynomial representation and manipulation.

This file provides utilities for converting symbolic expressions to polynomial form and extracting coefficient information.

Polynomial Representation

Many symbolic expressions in SDFGs are polynomial in nature. This module provides functions to convert expressions to polynomial form and extract structural information.

Affine expressions (degree 1 polynomials) are particularly important as they represent linear transformations commonly found in loop index calculations and memory addressing.

Example Usage

// Convert an expression to polynomial form and extract coefficients
auto i = symbolic::symbol("i");
auto j = symbolic::symbol("j");
auto expr = symbolic::add(symbolic::mul(symbolic::integer(2), i),
                         symbolic::add(symbolic::mul(symbolic::integer(3), j),
                                      symbolic::integer(5)));  // 2*i + 3*j + 5
 
SymbolVec symbols = {i, j};
auto poly = polynomial(expr, symbols);
auto coeffs = affine_coefficients(poly);
// coeffs[i] = 2, coeffs[j] = 3, constant = 5

See also

symbolic.h for building symbolic expressions