Re: Adding fast many polynomials of varying degrees

jeicke wrote:


Maybe somehow converting it into a regular MATLAB matrix first,
using
the function cell2mat, then using the function 'sum', would be
faster.

You also might look at using sparse matrices for P instead of a
cell
array. Are you using a cell array to do something similar as a
sparse
matrix?

That's my guess- and, although I've not used benchmarked cell
arrays
myself, I'd be shocked if they weren't much slower than non-cell
arrays.

Much depends upon what else you are doing with
these polynomials, and how you generate them.
A sparse form would make this sum much faster,
but other operations might be less fast.

If many of your polynomials are very short
and of the same length, then you might be able
to gain by

Lp = cellfun('length',P);

Now, use unique on the lengths Lp, separating
out all polynomials with the same lengths.
Use a cat operation to concatenate all of the
identified same length polynomials together,
then sum them, and accumulate into a total
summed polynomial.

Would this be more efficient than a brute
force sum? I have no way to tell without
knowing the distribution of lengths.

Another trick is to use sparse to directly
sum the polynomials. This might be fast.
Something like this:

P = {1:3 1 1:3 2:5};
S = sparse(1,cell2mat(cellfun(@(c) ...
length(c):-1:1,P,'UniformOutput',false)),cell2mat(P));
S = fliplr(full(S));

This code can surely be cleaned up.

HTH,
John D'Errico
.

Relevant Pages

  • Re: Proof that a Number is a Multiple of 3 If the Sum Of Its Digits in Decimal Notation Is a Multip
    ... decimal representation is a multiple of 3, ... Symbolic Sum Manipulation ... Induction via Integer Division Algorithm ... is essentially equivalent to passing to polynomials as I do in, ...
    (sci.math)
  • Re: Polynomial that satisfies integral condition
    ... because a_k is independent of m, we must have the sum hold for all ... In this case it directly follows since the hilbert matrix is ... The requirement essetially states that a_k be independent of m or da_k/dm = 0. ... Is not a *single* polynomial that satisfies the integral but the a set of polynomials where only one works at at time. ...
    (sci.math)
  • Re: Expressing a polynomial as a sum of squares
    ... > sum of squares of polynomials when such a representation exists? ...
    (sci.math.research)
  • Re: Polynomial Question
    ... I think in the first term you want a_i instead of a_1. ... elementary symmetric polynomials (which give the ... the sum of the k-th powers of the b_i are the same. ... invariant, so we might as well divide through by k. ...
    (sci.math.research)
  • Re: Subset Sum problem (w/ limited scope)
    ... The "Subset Sum" problem (stated various ways depending on what you ... a subset of those integers that sums up to zero. ... Are there going to be duplicate values in your original array? ...
    (comp.lang.fortran)
Loading