Let $f(x)=\sum_{i=1}^n p_i(x)$ be the expression we are attempting to simplify. One possible approach is to ask which $p_i$ can be the last polynomial of the simplification. To answer this, we can first use the $O(nlog(n))$ algorithm to compute the factorization of $f$. Say $f(x)=(ax+b)(cx+d)$. Then, the only possible choices for the last polynomial are the $p_i$'s that are divisible by $(ax+b)$ or $(cx+d)$. If we are lucky, there might only be one such choice, say $p_k$. We can then replace $f$ by $f-p_k$ and recurse. This approach will certainly work in the case that there is a unique ordering of simplification.
Let $f(x)=\sum_{i=1}^n p_i(x)$ be the expression we are attempting to simplify. One possible approach is to ask which $p_i$ can be the last polynomial of the simplification. To answer this, we can first use the $O(nlog(n))$ algorithm to compute the factorization of $f$. Say $f(x)=(ax+b)(cx+d)$. Then, the only possible choices for the last polynomial are the $p_i$'s that are divisible by $(ax+b)$ or $(cx+b)$. (cx+d)$. If we lucky, there might only be one such choice, say$p_k$. We can then replace$f$by$f-p_k$and recurse. This approach will certainly work in the case that there is a unique ordering of simplification. 1 Here's an idea (not a solution), which I thought I would post before heading out for coffee inspiration. Let$f(x)=\sum_{i=1}^n p_i(x)$be the expression we are attempting to simplify. One possible approach is to ask which$p_i$can be the last polynomial of the simplification. To answer this, we can first use the$O(nlog(n))$algorithm to compute the factorization of$f$. Say$f(x)=(ax+b)(cx+d)$. Then, the only possible choices for the last polynomial are the$p_i$'s that are divisible by$(ax+b)$or$(cx+b)$. If we lucky, there might only be one such choice, say$p_k$. We can then replace$f$by$f-p_k\$ and recurse. This approach will certainly work in the case that there is a unique ordering of simplification.