Dear Ralf,
Maybe we should think about the efficiency comparison "polynomial" vs
"monomial" first. I am CC'ing this explicitely to Nicolas and Joris, maybe one
of you has some idea of what is a good approach? In fact, I believe that this
is a very interesting question in its own right, it should apply to many
settings, very likely also symmetric functions etc.
Nicolas, Joris, if you do not mind, I will simply forward our discussion to
you, it would be wonderful if you could come up with some ideas! Or maybe you
know somebody who knows... Finally, I'd be also interested whether you know
about other contexts where the same problem appears.
-- introduction ---------------------------------------------------------------
We are discussing possible ways of storing certain formal power series in many
variables. (In fact, currently we are interested mainly in the cycle index
series of combinatorial species, but, I believe, this is nearly irrelevant)
We like to view these series as univariate formal power series, with the
coefficient of x^n being (in a certain sense) homogeneous polynomials of total
degree n.
Now, Ralf has implemented many operations on these power series, like addition,
multiplication, derivative, integration, (a certain plethystic) composition,
so-called functorial composition, Hadamard product, etc.
Now, when we were trying out the operation called "functorial composition", we
experienced an efficiency problem:
Currently, the smallest entity of our series are the polynomials. I.e., our
series are streams of polynomials. To compute the next coefficient of, for
example, the product of two series f and g, we simply have
sum_k=0..n [x^k] f [x^(n-k)] g
Now, for functorial composition, we suddenly do not need to know *all*
coefficients of monomials of a given total degree, but rather only very few,
which are, however, of *very* high degree.
With our current approach, this does not work well, since we always need to
compute *all* monomials of a given total degree.
Thus, we thought about switching to a monomial-based approach, where we would
have (roughly) a stream of lists of monomials. However, we are afraid that this
will slow down all the other operations: often we want to compute *all*
monomials of a certain degree. And in many cases, only very very few monomials
will have non-zero coefficient...
I'm not sure whether I was precise and clear enough. If I wasn't *please* tell
me so...
In the following, CIS is for "cycle index series", i.e., the series which
interest us. These are series in infinitely many variables x1,x2,x3,..., where
the total degree of a monomial
x1^n1 x2^n2 x3^n3 ...
is
n1 + 2 n2 + 3 n3 + ...
We call the (finite!) vector (n1, n2, n3,...) "cycletype".
As I hinted at before, we consider these series as streams of "homogeneous"
polynomials.
For certain reasons, we denote the series with Z_f, Z_g, etc.
--end of introduction----------------------------------------------------------
Post by Martin RubeyPost by Ralf HemmeckeAdditionally, assume I ask for the polynomial of degree n and in the data
structure p already has some terms but r is not zero (or not the empty
list), then what is the fastest way to compute the correct p? Should I
start computation for each of the elements in r or would it be wiser to
throw away p and r and compute p in a similar fashion as is done now, ie
always consider the polynomial of degree n as *one* thing?
Do you see an example where you really save time when you compute all
monomials at once - as you do it now?
One fact that might favor polynomial-oriented algorithms is that you do not
have to consider all monomials, rather, only those which are actually
there. This is important, for example, for species built only using Plus
and Times and Singletons, since in this case the CIS depends only on x_1.
[x^\sigma] Z_{f*g} =
[x^\sigma] Z_f*Z_g = \sum_{\tau <= \sigma} [x^\tau] Z_f
[x^{\sigma-\tau}] Z_g
which has to be done for all possible \sigma, vs the current implementation
Z_{f*g} = \sum_n \sum_k [x^n] Z_f * [x^{n-k}] Z_g
where
* n denotes total degree
* \sigma is a cycle type
* x^\sigma = x1^{\sigma_1} x2^{\sigma_2} ...
* [x^\sigma] Z_f denotes the coefficient in Z_f
* \tau <= \sigma is to be understood componentwise.
Post by Martin RubeyI'm too lazy to count operations right now. But I guess that it does make a
difference... For some reason, computing monomials we do not "see" as much
of the argument cycleindexfunctions Z_f and Z_g as if we were computing
polynomials.
You see the problem with the first thing term-wise approach is that I have to
loop over all cycle types even those that correspond to zero coefficients.
Yes. The zero coefficients are the bad ones :-)
However, if the user (or program) knows that she is going to need all
coefficients, she will certainly not ask the system to compute the coefficients
of the monomials termwise.
We are in trouble only if some of the coefficients have been already computed,
and in the next step we need all of them anyway.
So, the problem roughly goes like:
coefficient(f, (0,0,5)); -- compute a monomial of degree 15
coefficient(f, (1,1,4)); -- compute another monomial of degree 15
-- now, several monomials of degree 15 and very likely of lower degree, too
-- have been computed
coefficient(f, 5); -- compute all monomials of degree 5.
What is the last operation to do? Should we have a rule of thumb, depending on
the number of missing monomials and the total number of possible monomials...?
BTW, do you really think we (which probably means just me) should invest more
time into making cycle index series from polynomial-wise to term-wise? Wouldn't
it make more sense to just create SimpleGraph as
macro {
CS == CombinatorialSpecies;
E == SetSpecies;
E2 == RestrictedSpecies(E, 2);
WP == Times(E, E);
P2 == Times(E2, E);
}
SimpleGraph(L: LabelType): CS L == FunctorialCompose(WP, P2)(L) add;
and override the generic CIS and isomorphismTypeSeries with more efficient
versions?
No. This may be interesting for graphs, but the problem is a general one, it is
not even restricted to functorial composition. (Well, in the species world it
is. But I'd be surprised if the problem wouldn't pop up in other contexts, too)
And I think it is an interesting problem. Don't you?
Martin
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV