The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math.symbolic

Topic: 136 theorems on 29 pages
Replies: 20   Last Post: Nov 19, 2012 4:55 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 1,139
Registered: 4/26/08
Re: 136 theorems on 29 pages
Posted: Oct 1, 2012 4:31 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Waldek Hebisch schrieb:
> The existence of formulas is not in doubt -- it is part of proof
> of correctness of Hermite reduction.
> FYI, Hermite reduction starts with an ansatz:
> A*P_1^a_1*...*P_m^a_m = (B*P_1^(a_1+1)*...*P_m^(a_m+1))' +
> C*P_1^(a_1+1)*...*P_k^(a_k+1)P_{k+1}^a_{k+1}*...*P_m^a_m
> where P_i are relatively prime polynomials and A, B and C
> are polynomials. Denoting by n_1 sum of degrees of P_i for i in 1..k
> and by n sum of degrees of P_i for i in 1..m we require
> A be polynomial of degree at most n-1, C be at most of degree n - 2,
> while B at most of degree n_1 - 1.
> This leads to equation:
> A = B*S + B'*U + C*V
> where U=P_1*...*P_m, S = ((a_1+1)P_1'/P_1 + ... + (a_m + 1)P_m'/P_m)*U,
> V = P_1*...*P_k. Writing W = P_{k+1}*...*P_m, D = B'*W + C
> we get
> A = B*S + D*V
> It is easy to see that as long as all (a_i + 1) for i=1,...,k are nonzero
> S and V are relatively prime, so (by the extended euclidean algorithm)
> there exist polynomials u and w such that
> A = u*S + w*V
> Moreover, when we requre u to be at most of degree n_1 - 1 = deg(V) - 1
> the solution is unique, so B = u and D = w. Now C = w - B'*W and
> it is easy to see that C satisfies requested degree bound.
> This covers increasing a_i. For decreasing them argument is a bit
> longer but not much.

Thanks for writing this out. For one, it confirms the wisdom of the
author not to bother about proofs. I haven't gone through every detail,
but you seem to cover the case of rising exponents in the non-degenerate
integrands of the paper fully (I expect the P_i must somewhere be
required to be squarefree also). Your (and Hermite's) reference to the
extended Euclidean algorithm replaces my reference to solving a system
of linear equations. And via decomposition into linear factors and
chaining of recurrence relations, the degenerate cases are covered as

Unless this must count as your own work, the author will need suitable,
maybe original, references that cover the raising and lowering of
exponents in this way. While a limitation to rational integrands would
presumably be no problem, Hermite(*) has considered (for him without
loss of generality) isolated powers only, as also seen in Hardy's
account of 1916. The modern presentation in Bronstein's "Symbolic
Integration Tutorial", on the other hand, is too specialized: Bronstein
restricts the factor acted on to be that with the highest exponent, he
somehow omits the other factors from the integrated term, and he doesn't
analyze or discuss the numerator degrees. This is downright unsuitable.

(*) <>

> My points are:
> 1) While argument is simple the solvability of resulting system
> needs a proof.

Mathematicians would be and should be interested in a proof for general
order. I am not so sure about applied mathematicians or theoretical
physicists ... And engineers probably wouldn't and shouldn't.

> 2) The process is well-known as Hermite redution.
> 3) Since withing degree bounds solution is unique you must get
> exactly the same formulas

At least for raising exponents, the non-degenerate formulae in the paper
are just special cases of (a rather general formulation of the more or
less well-known process of) Hermite reduction for a generic given
numerator that matches the transformed numerator in degree.

> 4) At conceptual level it does not matter if you present this as
> rules or an algorithm: you perform exactly the same sequence
> of tranformations, using the same formulas. On practical level
> procedures are likely to solve systems of equations on the fly,
> while the paper presents precomputed formulas (and I agree that
> precomputed formulas are better if you insist on encoding
> Hermite reduction using rules).

I would say, mathematically the recurrence formulae in the paper and
Hermite reduction may be equivalent, or identical, or one a case of the
other. Conceptually, I perceive a vast difference between the
self-terminating reduction scheme as which the first is presented
normally, and relations cast as rules - be they precomputed or produced
on demand - which can be applied repeatedly to drive arbitrary exponents
in an integrand up or down as desired (as long as no zero determinant is
hit). It should be no accident that nobody refers to the integral
equation set up for Hermite reduction as a recurrence relation.

> 5) Clearly Hermite reduction counts as prior art for the article.

I don't think the author will have a problem with this insight.

> >
> > Agreed. But cases where this is absolutely crucial appear to be rare
> > when problems relating to the physical world are addressed by
> > integration.

> Avoiding unneeded algebraics is crucial if you want to do some
> symbolic computations with the result -- extra algebraics
> can cause huge slowdown.

I consider factorizations leading to at most square roots within square
roots acceptable; more complicated stuff should be handled as RootOf
objects anyway (along with the rules for their algebra). But meaningful
symbolic (non-numerical, parametrized) roots where this is needed tend
to be rare in science. Mathematical research differs perhaps.


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.