Week 9

Salut! This week was a bitter-sweet one. It was immensely frustrating and gratifying at the same time. I spent a large part of the week looking for hard to find bugs and fixing them. I'll attempt to list these nasty creatures below:

• The first one relates to a mistake in the construction of the list r in same_charclass? in the slope = 0 case. A ',' (comma) was used for combining two elements in the list but cons should have been used instead.
• A couple of more changes related to computing unsafe factors in factor_newton and avoiding repeated computations in factor_minmult1 were rendered redundant based on the final modification (more on it in the last point).
• I also fixed the order of multiplication in the adjoint case in try_factorization. Earlier, the inverse of the leading coefficient of srl was used as the left operand in the multiplication, though it should have been the right one.
• Operators passed as arguments to same_charclass? are now made monic  before further computation is performed on them. This avoids the errors arising from cases where the operators have different leading coefficients.
• I figured out that I was passing the wrong singularity and factor to factor_minmult1 and hence I changed the code so that factor_minmult1
  is no longer used. I now believe that the factorizer should work as far as the methods from chapters 2 and 3 are concerned.

"If you want to shine like a sun. First burn like a sun." -- Dr. APJ Abdul Kalam.

Week 8

Bonjour! This week, I modified factor_global to incorporate the remarks made regarding it on the mailing list. This involved adding infinity as a singularity only if it was known that infinity was not a regular point of the operator. A new function inf_singularity? was used for the same. Other changes included using rootOf instead of zerosOf for computing the roots of a factored polynomial and using already known factors instead of computing the lcm of denominators and then factoring. compute_bound was fixed to not ignore ramified exponential parts and compute the trace correctly. Further, code corresponding to the v'(e_i-e_j) term was also added. try_factorization(2) was altered to take advantage of the routine used to solve the Hermite-Padé problem posted by Waldek on fricas-devel. I also implemented an exported function to compute generalized exponents. It takes an operator and a point p as inputs (if p ~= 0, then it is moved to 0 and the result has x-p or 1/x if p = infinity in place of x). The output is a list of equivalence class of generalized exponents up to conjugation over Q((x)) [ecs, ecr, ect] where ecs is written in terms of ecr=ect.

This week, I intend to fix the remaining problems in the current code, if any, and move on to implementing the eigenring  related functions as described in chapter 5 of the van Hoeij thesis. The interesting thing about this method is that it works best for cases that are difficult to factorize via the methods in chapters 2 & 3, i.e, the routines implemented so far.

The next update will be posted (hopefully) in a weeks time ;)

Week 7

As mentioned in the previous post, this week I worked on extending factor_global which is basically the main function that is required to be implemented as the routine which is exported by the package, factor is like a wrapper. To do this the Padé approximation functions were added including lift_pade2, valuation_pade2, smaller_pade2?, wipe_pade2 and smallest_pade2. Currently, these do not use guessHolo as suggested on the mailing list, but will soon be changed. Also, this enabled me to complete try_factorization and try_factorization2. I also implemented the linchpin of this project, factor. However, it is not all rosy as calls to factor don't end for most input operators, but the function does work with the powers of D as arguments (maybe more, but I only tested with them). try_factorization takes as input a local factor, the maximal order to look for, Newton polygon bound, point of singularity, the global operator to be factored and the extra singularities bound and produces as output a global factorisation or "failed". It is made use of in factor_minmult1 and factor_global. factor_minmult1 takes a local factor R with multiplicity 1 and results in a factorization of f. If f is returned unfactored, then it is irreducible (if the specified bound is correct).

This week, I intend to straighten out the kinks remaining  in my code to ensure that the methods from chapters 2 and 3 of the van Hoeij thesis are correctly implemented. This Sunday marks the second milestone point of my project.

"May the force be with you" -- Star Wars.

Week 6

Sorry for the delay. There was a problem with the internet connection. Coming back to the task at hand, this week I wrote the documentation for the factor_* functions and their helpers. Now, all the subroutines related to factorization in the k((x))[xD] domain are complete. The small addition that I mentioned about last week regarding the splitting of coefficients in a basis of the algebraic expression in lift_rightfactor was also finished. There was a problem remaining in factor_riccati when the "split over k((x))" option was used but, that was resolved via a patch too OREPCTO.spad submitted by Waldek on the mailing list. I also implemented the same_charclass?, l_p and compute_bound functions. The same_charclass? function tests whether two irreducible operators have the same exponential parts. l_p(f) produces the localisation of f at the point x = p as mentioned in Section 3.3.4 of the van Hoeij thesis. compute_bound returns the bound for the number of extra singularities in a first order right factor. This week I intend to extend the factor_global routine which is already a work in progress and write the functions required for the same.

"May the odds be ever in your favor." -- Suzanne Collins.

Week 5

I'm truly having a blast this summer doing this project! Speaking of which, the project has reached its halfway and the mid-term evaluation are upon us.

Coming back to business, this week I implemented the coprime index > 1 factorization algorithm that takes a first order right hand factor with coefficients in an algebraic extension of k((x)) and produces an irreducible right hand factor belonging to k((x))[xD]. This involved the writing down of two functions, make_rightfactor and lift_rightfactor. The lift_rightfactor routine required the use of undetermined coefficients. Two options for representing the same were mentioned on the mailing list. One possibility was to use Polynomial(US) but this approach could be problematic as the domain performs a lot of comparisons of its coefficients to zero while doing its internal calculations. So, it was decided to go with Vector(US). Another decision was regarding what method to use while solving the resulting system of linear equations. Gaussian elimination might have had problems with finding pivots, so Cramer's rule was used instead. A small addition regarding splitting of coefficients in a basis of the algebraic extension is still to be finished in lift_rightfactor, after which I'll start with the global factorization subroutines.

"May the stars watch over you."  -- Christopher Paolini.

Week 4

Hope you have been taking good care of yourself! As mentioned in the previous post, the first thing I did last week was to resolve the bug in the function implementing step one of the pipeline, listream_coefs. So, now all the functions related to factorization via the Newton method work as expected. Hence, I added documentation for them.
I also wrote an initial version of the factor_riccati and the factor_op functions along with their helpers: substitute, ramification_of and iram_of. The factor_riccati function requires us to find the zero of a polynomial that is irreducible in F, the domain of coefficients. Two approaches for this task were mentioned on the mailing list - one was to use the domain SimpleAlgebraicExtension, but this approach had a problem with return values. Thus, I went with the second approach which is also used by the integrator viz. use Expression R (usually Integer) as the base domain.
This week, I plan to modify the factor_* routines according to the comments received and implement the coprime index > 1 algorithm. This will be followed by the global factorization methods. For further updates, stay tuned!

Week 3

This week I fixed a small problem in the lifting code regarding how I was initializing the start_D variable. Also, it was mentioned on the mailing list that the lifting step should be done in a lazy way (i.e. on demand). So, I changed the lift_newton function to an incremental version and added routines to proceed according to the following pipeline mentioned by Waldek:

stream of [l_extra, r_extra] --> list of streams of coefficients
  --> list of Laurent series --> operator

The last two steps of the pipeline were quite easy to implement. The main work involved was in the first step. There is still an issue remaining for step 1 regarding how to handle zero series and I'm working on resolving that at the moment. The next task for me is to add documentation for all the undocumented functions relating to factorization via the Newton method. This week, I look forward to really starting to write code for the Riccati solution based functions. Take care.