
Re: 136 theorems on 29 pages
Posted:
Oct 2, 2012 1:36 PM


clicliclic@freenet.de 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 n1, 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 nondegenerate > 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. UCP38, 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 hebisch@math.uni.wroc.pl

