Skip to content

Polynomial

Polynomial operations from mechestim. These wrap NumPy's polynomial functions with FLOP counting.

Cost Summary

Operation Cost Formula
polyval \(2 \cdot m \cdot \text{deg}\) (Horner's method)
polyadd, polysub \(\max(n_1, n_2)\)
polymul, polydiv \(n_1 \cdot n_2\)
polyfit \(2m \cdot (\text{deg}+1)^2\)
poly \(n^2\)
roots \(10n^3\) (companion matrix eigendecomposition)
polyder, polyint \(n\)

Examples

import mechestim as me

with me.BudgetContext(flop_budget=1_000_000) as budget:
    coeffs = me.array([1.0, -3.0, 2.0])  # x^2 - 3x + 2 (free)
    x = me.linspace(0, 5, 100)            # free
    y = me.polyval(coeffs, x)             # 2 * 100 * 2 = 400 FLOPs
    print(f"polyval cost: {budget.flops_used}")  # 400

API Reference

mechestim._polynomial

Counted polynomial operations for mechestim.

poly(seq_of_zeros)

Return polynomial coefficients from roots. Wraps numpy.poly.

Source code in src/mechestim/_polynomial.py 
194
195
196
197
198
199
200
201
202
203
204
205
def poly(seq_of_zeros):
    """Return polynomial coefficients from roots. Wraps ``numpy.poly``."""
    budget = require_budget()
    seq = _np.asarray(seq_of_zeros)
    # If 2D (square matrix), n = shape[0]; if 1D, n = len(seq)
    if seq.ndim == 2:
        n = seq.shape[0]
    else:
        n = len(seq)
    cost = poly_cost(n)
    budget.deduct("poly", flop_cost=cost, subscripts=None, shapes=(seq.shape,))
    return _np.poly(seq_of_zeros)

poly_cost(n)

Cost for poly: \(n^2\) FLOPs.

Source code in src/mechestim/_polynomial.py 
55
56
57
def poly_cost(n: int) -> int:
    """Cost for poly: $n^2$ FLOPs."""
    return max(n * n, 1)

polyadd(a1, a2)

Add two polynomials. Wraps numpy.polyadd.

Source code in src/mechestim/_polynomial.py 
87
88
89
90
91
92
93
94
95
96
97
98
def polyadd(a1, a2):
    """Add two polynomials. Wraps ``numpy.polyadd``."""
    budget = require_budget()
    a1 = _np.asarray(a1)
    a2 = _np.asarray(a2)
    n1 = len(a1)
    n2 = len(a2)
    cost = polyadd_cost(n1, n2)
    budget.deduct(
        "polyadd", flop_cost=cost, subscripts=None, shapes=(a1.shape, a2.shape)
    )
    return _np.polyadd(a1, a2)

polyadd_cost(n1, n2)

Cost for polyadd: max(n1, n2) FLOPs.

Source code in src/mechestim/_polynomial.py 
20
21
22
def polyadd_cost(n1: int, n2: int) -> int:
    """Cost for polyadd: max(n1, n2) FLOPs."""
    return max(n1, n2, 1)

polyder(p, m=1)

Differentiate a polynomial. Wraps numpy.polyder.

Source code in src/mechestim/_polynomial.py 
121
122
123
124
125
126
127
128
def polyder(p, m=1):
    """Differentiate a polynomial. Wraps ``numpy.polyder``."""
    budget = require_budget()
    p = _np.asarray(p)
    n = len(p)
    cost = polyder_cost(n)
    budget.deduct("polyder", flop_cost=cost, subscripts=None, shapes=(p.shape,))
    return _np.polyder(p, m=m)

polyder_cost(n)

Cost for polyder: n FLOPs (n = len of coeffs).

Source code in src/mechestim/_polynomial.py 
30
31
32
def polyder_cost(n: int) -> int:
    """Cost for polyder: n FLOPs (n = len of coeffs)."""
    return max(n, 1)

polydiv(u, v)

Divide one polynomial by another. Wraps numpy.polydiv.

Source code in src/mechestim/_polynomial.py 
166
167
168
169
170
171
172
173
174
175
def polydiv(u, v):
    """Divide one polynomial by another. Wraps ``numpy.polydiv``."""
    budget = require_budget()
    u = _np.asarray(u)
    v = _np.asarray(v)
    n1 = len(u)
    n2 = len(v)
    cost = polydiv_cost(n1, n2)
    budget.deduct("polydiv", flop_cost=cost, subscripts=None, shapes=(u.shape, v.shape))
    return _np.polydiv(u, v)

polydiv_cost(n1, n2)

Cost for polydiv: n1 * n2 FLOPs.

Source code in src/mechestim/_polynomial.py 
45
46
47
def polydiv_cost(n1: int, n2: int) -> int:
    """Cost for polydiv: n1 * n2 FLOPs."""
    return max(n1 * n2, 1)

polyfit(x, y, deg, **kwargs)

Least-squares polynomial fit. Wraps numpy.polyfit.

Source code in src/mechestim/_polynomial.py 
181
182
183
184
185
186
187
188
def polyfit(x, y, deg, **kwargs):
    """Least-squares polynomial fit. Wraps ``numpy.polyfit``."""
    budget = require_budget()
    x = _np.asarray(x)
    m = len(x)
    cost = polyfit_cost(m, deg)
    budget.deduct("polyfit", flop_cost=cost, subscripts=None, shapes=(x.shape,))
    return _np.polyfit(x, y, deg, **kwargs)

polyfit_cost(m, deg)

Cost for polyfit: 2 * m * (deg+1)^2 FLOPs.

Source code in src/mechestim/_polynomial.py 
50
51
52
def polyfit_cost(m: int, deg: int) -> int:
    """Cost for polyfit: 2 * m * (deg+1)^2 FLOPs."""
    return max(2 * m * (deg + 1) ** 2, 1)

polyint(p, m=1, k=None)

Integrate a polynomial. Wraps numpy.polyint.

Source code in src/mechestim/_polynomial.py 
134
135
136
137
138
139
140
141
142
143
def polyint(p, m=1, k=None):
    """Integrate a polynomial. Wraps ``numpy.polyint``."""
    budget = require_budget()
    p = _np.asarray(p)
    n = len(p)
    cost = polyint_cost(n)
    budget.deduct("polyint", flop_cost=cost, subscripts=None, shapes=(p.shape,))
    if k is None:
        return _np.polyint(p, m=m)
    return _np.polyint(p, m=m, k=k)

polyint_cost(n)

Cost for polyint: n FLOPs (n = len of coeffs).

Source code in src/mechestim/_polynomial.py 
35
36
37
def polyint_cost(n: int) -> int:
    """Cost for polyint: n FLOPs (n = len of coeffs)."""
    return max(n, 1)

polymul(a1, a2)

Multiply polynomials. Wraps numpy.polymul.

Source code in src/mechestim/_polynomial.py 
149
150
151
152
153
154
155
156
157
158
159
160
def polymul(a1, a2):
    """Multiply polynomials. Wraps ``numpy.polymul``."""
    budget = require_budget()
    a1 = _np.asarray(a1)
    a2 = _np.asarray(a2)
    n1 = len(a1)
    n2 = len(a2)
    cost = polymul_cost(n1, n2)
    budget.deduct(
        "polymul", flop_cost=cost, subscripts=None, shapes=(a1.shape, a2.shape)
    )
    return _np.polymul(a1, a2)

polymul_cost(n1, n2)

Cost for polymul: n1 * n2 FLOPs.

Source code in src/mechestim/_polynomial.py 
40
41
42
def polymul_cost(n1: int, n2: int) -> int:
    """Cost for polymul: n1 * n2 FLOPs."""
    return max(n1 * n2, 1)

polysub(a1, a2)

Subtract two polynomials. Wraps numpy.polysub.

Source code in src/mechestim/_polynomial.py 
104
105
106
107
108
109
110
111
112
113
114
115
def polysub(a1, a2):
    """Subtract two polynomials. Wraps ``numpy.polysub``."""
    budget = require_budget()
    a1 = _np.asarray(a1)
    a2 = _np.asarray(a2)
    n1 = len(a1)
    n2 = len(a2)
    cost = polysub_cost(n1, n2)
    budget.deduct(
        "polysub", flop_cost=cost, subscripts=None, shapes=(a1.shape, a2.shape)
    )
    return _np.polysub(a1, a2)

polysub_cost(n1, n2)

Cost for polysub: max(n1, n2) FLOPs.

Source code in src/mechestim/_polynomial.py 
25
26
27
def polysub_cost(n1: int, n2: int) -> int:
    """Cost for polysub: max(n1, n2) FLOPs."""
    return max(n1, n2, 1)

polyval(p, x)

Evaluate a polynomial at given points. Wraps numpy.polyval.

Source code in src/mechestim/_polynomial.py 
70
71
72
73
74
75
76
77
78
79
def polyval(p, x):
    """Evaluate a polynomial at given points. Wraps ``numpy.polyval``."""
    budget = require_budget()
    p = _np.asarray(p)
    x = _np.asarray(x)
    deg = len(p) - 1
    m = x.size
    cost = polyval_cost(deg, m)
    budget.deduct("polyval", flop_cost=cost, subscripts=None, shapes=(p.shape, x.shape))
    return _np.polyval(p, x)

polyval_cost(deg, m)

Cost for polyval: Horner's method = 2 * m * deg FLOPs.

Source code in src/mechestim/_polynomial.py 
15
16
17
def polyval_cost(deg: int, m: int) -> int:
    """Cost for polyval: Horner's method = 2 * m * deg FLOPs."""
    return max(2 * m * deg, 1)

roots(p)

Return the roots of a polynomial with given coefficients. Wraps numpy.roots.

Source code in src/mechestim/_polynomial.py 
211
212
213
214
215
216
217
218
def roots(p):
    """Return the roots of a polynomial with given coefficients. Wraps ``numpy.roots``."""
    budget = require_budget()
    p = _np.asarray(p)
    n = len(p) - 1  # degree = number of roots
    cost = roots_cost(n)
    budget.deduct("roots", flop_cost=cost, subscripts=None, shapes=(p.shape,))
    return _np.roots(p)

roots_cost(n)

Cost for roots: \(10n^3\) FLOPs (companion matrix eigendecomposition).

Source code in src/mechestim/_polynomial.py 
60
61
62
def roots_cost(n: int) -> int:
    """Cost for roots: $10n^3$ FLOPs (companion matrix eigendecomposition)."""
    return max(10 * n**3, 1)