User:Mfasi: Difference between revisions
| Line 69: | Line 69: | ||
* implement a function to find a confluent permutation (a very specific task). | * implement a function to find a confluent permutation (a very specific task). | ||
The functions that should be addressed after that one are expm (), logm () and sqrtm (). The implementation of the first function is stable as it exploits Padé approximants, but could be improved using an heuristic that switches to some other kind of evaluation when such rational functions are ill-conditioned. The logm () functions is a recent implementation and uses a scaling and squaring method. Maybe some | The functions that should be addressed after that one are expm (), logm () and sqrtm (). The implementation of the first function is stable as it exploits Padé approximants, but could be improved using an heuristic that switches to some other kind of evaluation when such rational functions are ill-conditioned. The logm () functions is a recent implementation and uses a scaling and squaring method. Maybe some improvements can be done, since it computes just the principal matrix logarithm, not allowing the user to choose different branches. I would not touch sqrtm () instead, since it seems to be a good C++ implementation of an algorithm by Higham that should be very similar to the one in Matlab. I would instead focus on developing the p-th root, as there is a [http://poisson.phc.unipi.it/~maxreen/bruno/pdf/B.%20Iannazzo%20and%20C.%20Manasse%20-%20A%20Schur%20logarithmic%20algorithm%20for%20fractional%20powers%20of%20matrices%20-%20SIMAX.pdf recent work] that seems promising, though being rather involved it could be tricky to implement in a robust way. | ||
The hyperbolic and trigonometric functions have already been written down straightforwardly in thfm (), from the linear-algebra package. As it relies on sqrtm (), expm () and logm (), it will benefit of all the improvements to such functions. | The hyperbolic and trigonometric functions have already been written down straightforwardly in thfm (), from the linear-algebra package. As it relies on sqrtm (), expm () and logm (), it will benefit of all the improvements to such functions. | ||
Revision as of 08:39, 17 March 2014
Introduction
- I guess the three required sentences are on current studies, spoken languages and overall background. So:
- I am a student at "Ecole Normale Superieure" in Lyon (FR), second year of Master in Computer Science.
- Italian is my mother tongue, I use somehow English and French.
- I would say that my field is numerical analysis.
- As the project I am intested in is related to the domain I would apply for my Phd, I hope to boost a little my future applications. Moreover, I used the Octave functions I would work with for some Octave code I wrote.
- No previous experience with the Google Summer of Code
- I am choosing Octave on the one hand because is the organization I am most interested in out of the GSoC ones, on the other because it is probably the one that produces the software I know better.
Contact
- My nickname on IRC will be mfasi.
- I think my time zone will be CET UTC+1 - CEST UTC+2 (due to the Daylight Saving Time)
- Just now, I am working for an internship and I go to my office at 7.00 and leave at 18.00 (in UTC+0), but I do not spend all of the time coding. I guess I spend usually the last 4/5 hours doing so, while in the morning I prefer reading papers or developing some ideas (that will be coded later on).
Coding experience
- Experience with C++, Octave or Matlab m-scripts, OpenGL and Qt.
C++ and OpenGL where subjects of two university courses I've attended. I have used Octave to write my [https://dl.dropboxusercontent.com/u/37286377/thesis.pdf bachelor thesis.
- As a computer science student, I have had to work with many different languages:
- Imperative: pascal, C, Bash scripting, Java, JavaScript, PHP
- Functional: OCaml, HOPE
- Markup: LaTeX, XML, XSL, HTML
- Other: some SQL-based languages
- I have worked for some time to an open source project called Balcony (25K+ lines, C++), developed in Italy, whose aim was to build a virtual desktop to be installed on a USB key. The project was closed some years ago for lack of funds. I have also worked with a small team to produce an experimental service of automatic diseases classification from medical reports. As far as I know, the project is still maintained and developed, though it is not open source. Another non-opensource big project I took part to, for a little while.
- Contributions to Octave
Feeling fine
- Ny experience with
- IRC and mailing lists: I have used both of them, but I do not know more than 2 or 3 IRC commands by hart. There are reference chart for that, though.
- Mercurial: As I am implementing some patches for Octave, I am using it.
- Mediawiki: I have used it sometimes. By the way, I am using it right now.
- make, gcc, gdb or other development tools: I know how to write a Makefile, how to use a compiler and a debugger from both the command line or an IDE interface.
- When GSoC will be over, I think I will remain into Octave community because I will have gotten started. After having spent three months developing for Octave, I will know it enough to not be scared by the idea of picking an issue and solve it.
Only out of interest
- Actually I have been using Octave for four years now, but just as a user. I think you could advertise in math forums, there is plenty of them.
- I had trouble finding a GUI, but that is no longer the case. In general everything is well documented. I had some troubles, years ago, when trying to use the symbolic packagem that was not very well documented, as far as I remember.
Prerequisites
- I am granted the access to use any Linux Distribution (I can just install it on a PC), but the ones I've used are Debian, Ubuntu, Arch and Gentoo. I have also access machines with Windows 7 and 8.
- I think I will not have problems accessing a pc with internet during the GSoC period.
- I will be free to install new programs on all the operating systems described above.
Self-assessment
- As I know almost nothing about the Octave development cycle, I must rely on constructive criticism to improve my work. Moreover, as far as it is useful, as marked in the question, and polite, I am fine with it.
- I prefer studying the problem before start typing, writing down my ideas and having a clear picture of what are the modules I will have to implement. If the project is very though, I usually start coding from the smallest units, that are supposed to solve the simpler tasks, and building the more complicated ones on the top of them. As I value the time I spend coding, I do not like too much throw away my work, though it happens, sometimes, when I am not careful enough during the analysis step.
Your task
The project I would like to work on is the one called Improve logm, sqrtm, funm. Basically, I would like to provide Octave with an (almost) state of the art library to compute the most diffused matrix functions in a robust way. Octave's standard library as well as the linear algebra package (Octave Forge) already implement some of these functions, notably funm (), expm (), logm() and sqrtm(). Some of these implementations are good, while others should be improved or, in some cases, completely rewritten.
One of the functions that should be completely reimplemented is probably funm (), that currently uses a simple but in some cases weak approach inspired by the definition of matrix function via the Jordan canonical form. This approach fails when the matrix is not diagonalizable and can be very inaccurate when the eigenvectors are ill-conditioned. To avoid these issues I would like to use the Schur-Parlett recurrence with block reordering, a well known algorithm that though having some issues that should be addressed, is theoretically robust. This implementation will require to:
- modify the Schur function to deal with a specific reordering of the eigenvalues;
- implement a function that evaluates matrix polynomials using the Paterson-Stockmeyer scheme;
- implement a function to find a block pattern (how to group the eigenvalues of the Schur form);
- implement a function to find a confluent permutation (a very specific task).
The functions that should be addressed after that one are expm (), logm () and sqrtm (). The implementation of the first function is stable as it exploits Padé approximants, but could be improved using an heuristic that switches to some other kind of evaluation when such rational functions are ill-conditioned. The logm () functions is a recent implementation and uses a scaling and squaring method. Maybe some improvements can be done, since it computes just the principal matrix logarithm, not allowing the user to choose different branches. I would not touch sqrtm () instead, since it seems to be a good C++ implementation of an algorithm by Higham that should be very similar to the one in Matlab. I would instead focus on developing the p-th root, as there is a recent work that seems promising, though being rather involved it could be tricky to implement in a robust way.
The hyperbolic and trigonometric functions have already been written down straightforwardly in thfm (), from the linear-algebra package. As it relies on sqrtm (), expm () and logm (), it will benefit of all the improvements to such functions.
The choice of the test cases is not so trivial. For the funm () function, I think that could be worth testing the Schur-Parlett approach on exp (), log () and root(), as a comparison can be directly made with their matrix counterparts already present in Octave's core library. A few special functions should be tested too, and I would like to use the Bessel functions, the Dawson function and the Lambert one. For the expm () functions some of the test cases should address the values the Padé approximants are ill-conditioned for, to check whether the devised heuristic is effective and whether the new approach makes the implementation actually more robust. As logm () and rootm () are multivalued complex functions, the neighbourhoods of the branching points and of the branch cuts should be carefully tested, to ensure that our implementation is exactly respondent to the most accepted specifications.
Tentative timeline
- 21 April: Submission of an extended proposal to the mentor
- 19 May: Beginning of the coding period
- 30 May: Implementation of the auxiliary functions required for funm () (see above)
- 23 June: Implementation of funm () along with its test cases
- 31 July: Improvement of expm () and logm (), implementation of rootm () and check of the functionalities of thfm ()
- 7 August: Test cases for expm (), logm (), rootm () and thfm ()
- 18 August: End of GSoC program
- Later: Maintenance of the library
In bold, beginning of the program, mid-term and final evaluations deadlines.