Detect if a chebyshev polynomial has a simpler monomial basis representation
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
In the lowering of a Chebyshev polynomial evaluation, we use this Paterson-Stockmeyer method along with baby-step giant-step to optimize the circuit. However, in some cases, even this method produces something that is suboptimal.
For example, the Chebyshev polynomial `[0.0, 0.75, 0.0, 0.25]` (ordered low-to-high degree) is equivalent in the monomial basis to x^3, and if you lower this via PS-Chebyshev (test case below), you get
```
module {
func.func @chebyshev(%arg0: f32) -> f32 {
%cst = arith.constant 5.000000e-01 : f32
%0 = arith.mulf %cst, %arg0 : f32
%cst_0 = arith.constant 5.000000e-01 : f32
%1 = arith.mulf %cst_0, %arg0 : f32
%cst_1 = arith.constant 2.000000e+00 : f32
%2 = arith.mulf %arg0, %arg0 : f32
%3 = arith.mulf %cst_1, %2 : f32
%cst_2 = arith.constant 1.000000e+00 : f32
%4 = arith.subf %3, %cst_2 : f32
%5 = arith.mulf %1, %4 : f32
%6 = arith.addf %0, %5 : f32
return %6 : f32
}
}
```
This is nontrivially more complex than the naive monomial evaluation of x^3, and since we know the chebyshev polynomial statically at compile time, it may provide some gains to identify when:
- The monomial basis does not have numerical stability issues with its coefficients (i.e., large degree coefficients that are very small)
- The monomial basis evaluation circuit would be simpler than the ps-cheb evaluation circuit.
In that case we should either (a) switch to the monomial basis and lower with a method like horner (or monomial-basis ps), or (b) analyze the circuit post-hoc for algebraic simplifications.
```
// RUN: heir-opt --lower-polynomial-eval="method=pscheb" %s | FileCheck %s
!poly_ty = !polynomial.polynomial>
#poly = #polynomial.typed_chebyshev_polynomial<[0.0, 0.75, 0.0, 0.25]> : !poly_ty
module {
func.func @chebyshev(%ct: f32) -> f32 {
%ct_0 = polynomial.eval #poly, %ct {coefficients = [0.0, 0.75, 0.0, 0.25], domain_lower = -1.000000e+00 : f64, domain_upper = 1.000000e+00 : f64} : f32
return %ct_0 : f32
}
}
```
Contributor guide
Assessment
This issue has not been assessed yet.