From: Gene on
On Mar 15, 2:09 am, arun <arunw...(a)gmail.com> wrote:
> I am trying to solve the problems in "Data Structures and Algorithm
> Analysis in C".
> One of the questions asks you to find algorithms to find the product
> of two polynomials. The polynomials are represented using linked
> lists. The terms in the list may not be in sorted order. However the
> product itself should be a linked list where there is a single term
> for any power and is sorted by exponent.
>
> So its like ax^0 + bx^1 + ... + nx^n
>
> Finding an algorithm which does this in O((mn)^2) is easy (m and n are
> lengths of the polynomials). However the question is to find
> algorithms which can do this in O(nm^2) (m is the length of the
> shorter polynomial) and in O(mn log(mn)).
>
> I haven't been able to figure this out even after trying hard. I don't
> want complete solution (I know that this could be given as a homework
> problem), just some hints or pointers which will help me solve this
> problem.
>
> thanks,
> Arun

A different way to think about this problem is to note that you can
uniquely specify a polynomial of degree k with k+1 points. So pick k
+1 values of x, evaluate both polynomials at these x values, multiply
these k+1 pairs, then find the unique polynomial that passes through
the resulting points. The initial evaluation doesn't need the terms
in sorted order, so there are no sorting costs. Finding the resultant
polynomial requires expanding the Lagrange interpolant. I'll let you
all work out how quickly this can be accomplished. The more
sophisticated algorithms consider the multiplication as a convolution.
Convolution in cartesian space is pointwise multiplication in the
frequency domain. So take the FFT of the coefficients, multiply
pointwise, take the reverse FFT, and be happy.
From: Patricia Shanahan on
Gene wrote:
> On Mar 15, 2:09 am, arun <arunw...(a)gmail.com> wrote:
>> I am trying to solve the problems in "Data Structures and Algorithm
>> Analysis in C".
>> One of the questions asks you to find algorithms to find the product
>> of two polynomials. The polynomials are represented using linked
>> lists. The terms in the list may not be in sorted order. However the
>> product itself should be a linked list where there is a single term
>> for any power and is sorted by exponent.
>>
>> So its like ax^0 + bx^1 + ... + nx^n
>>
>> Finding an algorithm which does this in O((mn)^2) is easy (m and n are
>> lengths of the polynomials). However the question is to find
>> algorithms which can do this in O(nm^2) (m is the length of the
>> shorter polynomial) and in O(mn log(mn)).
>>
>> I haven't been able to figure this out even after trying hard. I don't
>> want complete solution (I know that this could be given as a homework
>> problem), just some hints or pointers which will help me solve this
>> problem.
>>
>> thanks,
>> Arun
>
> A different way to think about this problem is to note that you can
> uniquely specify a polynomial of degree k with k+1 points. So pick k
> +1 values of x, evaluate both polynomials at these x values, multiply
> these k+1 pairs, then find the unique polynomial that passes through
> the resulting points. The initial evaluation doesn't need the terms
> in sorted order, so there are no sorting costs. Finding the resultant
> polynomial requires expanding the Lagrange interpolant. I'll let you
> all work out how quickly this can be accomplished. The more
> sophisticated algorithms consider the multiplication as a convolution.
> Convolution in cartesian space is pointwise multiplication in the
> frequency domain. So take the FFT of the coefficients, multiply
> pointwise, take the reverse FFT, and be happy.

Remember that we don't know the degree of the input polynomials, only
the lengths of their representations. We could have a very short
polynomial of degree 1000.

Patricia
From: Pascal J. Bourguignon on
Patricia Shanahan <pats(a)acm.org> writes:

> Remember that we don't know the degree of the input polynomials, only
> the lengths of their representations. We could have a very short
> polynomial of degree 1000.

But the degree of such a polynomial representation can be determined in
O(length) which is good.

--
__Pascal Bourguignon__
From: Kai-Uwe Bux on
Pascal J. Bourguignon wrote:

> Patricia Shanahan <pats(a)acm.org> writes:
>
>> Remember that we don't know the degree of the input polynomials, only
>> the lengths of their representations. We could have a very short
>> polynomial of degree 1000.
>
> But the degree of such a polynomial representation can be determined in
> O(length) which is good.

True, but finding the product p*q using interpolation will still require
some deg(p)+deg(q) evaluations of the product. When deq(p) and deg(q) are
large compared to the input length, you exceed the allowed complexity, e.g.:

O( len(p) * len(q) * log( len(p) * len(q) ) )


Best

Kai-Uwe Bux
From: Patricia Shanahan on
Kai-Uwe Bux wrote:
> Pascal J. Bourguignon wrote:
>
>> Patricia Shanahan <pats(a)acm.org> writes:
>>
>>> Remember that we don't know the degree of the input polynomials, only
>>> the lengths of their representations. We could have a very short
>>> polynomial of degree 1000.
>> But the degree of such a polynomial representation can be determined in
>> O(length) which is good.
>
> True, but finding the product p*q using interpolation will still require
> some deg(p)+deg(q) evaluations of the product. When deq(p) and deg(q) are
> large compared to the input length, you exceed the allowed complexity, e.g.:
>
> O( len(p) * len(q) * log( len(p) * len(q) ) )

Or, for the case that I find troubling:

O( len(p) * len(q) * len(q) ) where p is the longer input.

Maybe the person setting the problem assumed degree and length were
equivalent, but then it is hard to see why the target complexities are
so high.

Patricia