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.

Week 2

In the second week, I implemented the lift_newton function that is used to lift coprime index 1 factorizations. plug_delta, coeffx, coefs_operator and coefs_poly were the helper functions used in the process. coefs_operator takes a polynomial and returns an operator with the given valuation, while coefs_poly takes an operator and returns a polynomial after extracting its relevant part. plug_delta simply converts a polynomial to a differential operator by substituting δ = xD in place of x. coeffx(f, e) returns the coefficient of x^e in f while simultaneously substituting x in the place of δ. The initial version of lift_newton that I implemented was buggy, but thanks to the review on the mailing list, I was able to correct it. The plan now is to tie up any loose ends in the functions finished so far which all deal with factorization using the Newton method. If there are no more problems with them, then I'll go on to implement the functions related to factorization using a Riccati solution : factor_riccati and ramification_of. That's all from me. Good-bye, until next time.

GSoC 2015 - Week 1

My proposal "Factorization of LODOs in FriCAS - the van Hoeij algorithm" has been accepted for Google Summer of Code 2015. So, I'll again be working under lmonade this summer (and I'm glad to be working under the same umbrella organization). My mentors for this project are Waldek Hebisch and Ralf Hemmecke. The official coding period began last week (May 25) and so I have started to code. The source code can be found here.

I've finished the implementation of the newtonpolygon function that returns the extreme points of the Newton polygon, the associated slopes and Newton polynomials of an operator.
Further, I also implemented the factor_newton function that performs coprime index 1 factorizations for which the op_with_slope function was a helper. However, the lifting step of the algorithm is still to be done and that is what I'm working on at present. So, the plan for this week is to finish the algorithm for coprime index 1 factorizations by implementing lift_newton and coefs_operator. I was a little stuck about how to actually implement the lifting algorithm, but Waldek clarified my doubts to a large extent on the fricas-devel mailing list. I'm still not completely confident but am able to work on the functions, so I guess I'll finish the implementation first and then modify it according to the comments received. Okay, that's it for now. See you next week!