Abhinav Baid wrote:
>
> I've implemented the factor_newton function (it isn't complete yet, as
> the lifting algorithm has not been implemented and so, I haven't added
> the documentation). Could you please review it? [1]
1) the 'flagv' variable is ugly. In the inner loop vif does not
change and its degree does not change, so you can compute then
outside of inner loop and reuse. It makes sense to divied 'e'
by degree of 'vif' first and only later test if the result is
an integer. AFAICS this will simplify the logic. Also, if
you need to skip several instructions in sequence use something
like
-- computation
cond => "skip"
-- another computation
Note: '=>' mean exit seqence producing given value. In context
when value is not needed anyting can be given but "skip" serves
as a comment. If the intent is to go to next iteration of a
loop then "iterate" is be better.
> Also, I'm a little stuck at the moment as I can't figure out how to
> actually implement the lift algorithm. My understanding so far is that
> the current code will produce 2 truncated factors : L' and R' which need
> to be lifted to get the required factorization f = LR. Now, my doubt is
> that to do this we'll have to use l and r such that L'' = L'+l and R'' =
> R'+r are better approximations of L and R. We do this using a condition
> on the valuation of l and r and use indeterminates for the unknown
> coefficients and solve the resulting system of linear equations. Any
> pointers on how do I do all this in the lift_newton function would be
> greatly appreciated. Also, the in the current code, I include the term
> xD^(n - pd) in L' where n is degree(f) and pd is degree(R'). I'm not
> really sure if this is correct. Should I instead include that term in l?
ATM you need only coprime index 1 case. It can be done in simple
way and much more efficiently than the general case, in particular
there is no need to introduce indeterminate coefficients. So
it make sense to do this and later do coprime index > 1. Multiplying
L'' and R'' you get
L''R'' = (L' + l)(R' + r) = L'R' + L_0r + lR_0 + terms with higher valuation
So you need to extrac lowest valuation part e_n from f - L'R' and
solve equation
e_n = L_0r + lR_0 mod terms with higher valuation
where L_0 and R_0 are lowest valuation parts of L' and R'. When
slope > 0 modulo higher valuation parts this is essentially
polynomial multiplication and the equation can be solved using
extended Euclidean algoriithm. In particular for given polynomial
p = p1 p2 with coprime p1 nad p2 one can find polynomials c1 and
c2 such that
1 = c1*p1 + c2*p2 mod p
then solution to
g = d1*p1 + d2*p2
with deg(d1) < deg(p2) is given by
(S) d1 = g*c1 mod p2
d2 = (g - d1*p1)/p1
(the second division must be exact).
Fricas has 'extendedEuclidean' function which computes c1 and c2.
For slope 0 thing are a bit more complicated, because instead of
plain polynomial multiplication left terms get shifted
but you still can use essentially the same method, only polynmial
corresponding to L_0 is shifted in each step and you need to compensate
for shift when recovering l from polynomial.
In fact, when working with operators you need to take care of
mapping between polynomials and operators of valuation s. For slope 0 this
mapping is very easy: you just plug in \delta = xD into the
polynomial and multiply by x^s (but you need to take into account
shifts due to multiplication formula). For slope > 0, there are
extra shifts because terms of operator correspond to integer point
and you are looking at intesection of sloped line with integer
points inside Neton polygon. Due to shift leftmost point will
change. If slope is n/d the extra shift will have period d.
Concerning your question about (xD)^(n - pd) term. You need to
add it to left factor to make it monic. Lifting only corrects
lower order terms, and assumes that highest order term is
uniqely determined by normalization. Due to definition of
Newton polygon lowest valuation part of f is normally of lower
order than f. In other words, highest order term in f has
higher valuation. During lifting at first the (xD)^(n - pd) term
will play no role (because you are dealing with lower valuations),
but later is important (it affect error terms). Wheter you add
(xD)^(n - pd) before lifting or during lifting first time
when it is needed is a detail. For example if you keep
in L' only terms with valuation <= s, than it is natural
to add (xD)^(n - pd) when you reach its valuation.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
