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 ]
Waldek Hebisch

Posts: 267
Registered: 12/8/04
Re: 136 theorems on 29 pages
Posted: Oct 2, 2012 1:36 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply wrote:
> 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).

Yes, P_i should be squarefree -- this implies that P_i' and P_i
are relatively prime.

> 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
> well.
> 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.

AFAICS Bronstein follows D. Mack here. OTOH Bronstein code in FriCAS
contains comment:

-- Hermite Reduction on f, every squarefree factor of denom(f) is normal wrt D
-- this is really a "parallel" Hermite reduction, in the sense that
-- every multiple factor of the denominator gets reduced at each pass
-- so if the denominator is P1 P2^2 ... Pn^n, this requires O(n)
-- reduction steps instead of O(n^2), like Mack's algorithm
-- (D.Mack, On Rational Integration, Univ. of Utah C.S. Tech.Rep. UCP-38, 1975)
-- returns [g, b, d] s.t. f = g' + b/d and d is squarefree and normal wrt D

And accordinng to the comment code reduces all exponents.

I affraid there is no good reference: what I wrote above is obvious
for somebody who read and deeply understand the papers (say Rothstein,
Trager and Bronstein thesis), but no luck if you want exactly
the same setting -- note that if you deal with rational functions
there is no motivation to track exponents you do not reduce.

IIRC both Trager and Bronstain in thesis handling algebraic integrands
reduce just highest exponent, while the Bronstien code actually reduces
all exponents it can. In other words, "everbody" (at least Bronstein)
knows that process is more general, but to simplify exposition
they present only specialized versions.

Waldek Hebisch

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.