
Re: 136 theorems on 29 pages
Posted:
Oct 4, 2012 2:26 AM


Waldek Hebisch schrieb: > > 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.
These are my conclusions:
For a citation in the author's paper to be helpful and perhaps 'required', the parallel update of a range of exponents 1 to k is of course unnecessary, a restriction to k=1 would suffice. Any suitable exposition, however, should readily generalize to noninteger exponents, although this possibility need not be stated explicitly. Thus, Hardy's account (*) of Hermite's method is clearly applicable to the case of raising a noninteger exponent of an isolated nondegenerate factor, whereas Bronstein's account of the modern method is not recognizably applicable to the case of raising a noninteger exponent of one factor among other algebraic factors. And citing inaccessible theses and internal reports can be more frustrating than helpful to a reader (as well as dangerous to an author who never saw them).
(*) following Goursat's Cours d'analyse mathÃ©matique, tome 1, of 1902, <http://wwwhistory.mcs.standrews.ac.uk/Extras/Goursat_cours_d_analyse.html>
It looks like a review of "Variations on modern Hermite reduction" is needed, and that you would be the right person to write it :). This could include the raising and lowering of a single noninteger exponent, a generalizion to Macktype parallel versions for efficiency reasons, a look into variations and simplifications for rational integrands from Bronstein to ... to Goursat to Hermite, and an analysis of numerator degrees leading to recurrence relations for algebraic integrands of arbitrary order. It wouldn't matter that Bronstein must have known more than he committed to paper, his contributions could be acknowledged in a manner like that used by R.E. Crandall in his "Unified algorithms for polylogarithm, Lseries, and zeta variants",
<http://www.perfscipress.com/papers/UniversalTOC25.pdf>.
Martin.

