An Approximate Decomposition of a Multivariate Polynomial and Its Application

Abstract Given a multivariate polynomial f , we consider an approximate decomposition in the Hamming distance, that is, $${f}{=} {g} {\circ } {h} \,{+ \, \delta },$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>=</mml:mo> <mml:mi>g</mml:mi> <mml:mo>∘</mml:mo> <mml:mi>h</mml:mi> <mml:mspace/> <mml:mrow> <mml:mo>+</mml:mo> <mml:mspace/> <mml:mi>δ</mml:mi> </mml:mrow> <mml:mo>,</mml:mo> </mml:mrow> </mml:math> where g is a univariate polynomial, h and $${\delta }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> are multivariate polynomials, and $${\delta }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> has few terms. We propose an algorithm for computing an approximate decomposition and introduce its application to multivariate Horner’s scheme.