User:Edu159: Difference between revisions

Jump to navigation Jump to search
132 bytes removed ,  20 March 2014
Line 95: Line 95:


== Y: Your task ==
== Y: Your task ==
My intention is upgrading  some functions related with sparse matrices  so they become compliant with Matlab  and implement others that are not present in Octave right now.
My intention is to implement the missing '''ilu''' and '''ichol''' functions and continue last year GSoC project developed by Kai Torben. The goal is the complete integration in the core branch of Octave. Those functions will have a direct impact on quite a few functions that solve sparse linear systems as ilu and ichol are known to be good algorithms for generating good preconditioners. Some of the functions that will take advantage of them are pcg, bicg or gmres among others. Bottom line performance of sparse linear system solvers will be raised. The approach and timeline for the project are described below.
The functions are '''ichol''', '''ilu''', '''sprand''', '''sprandn''', '''sprandsym''', '''minres''' and '''lsqr'''.  


*'''Approach:'''
*'''Approach:'''


**'''ilu:''' That function has a big chunk of options and the last year was almost implemented by Kai Torben as his GSOC [http://siko1056-gsoc.blogspot.de/ project]. He interfaced Octave with ITSOL/ZITSOL libraries but in the end there were some issues with that approach:
**'''ilu:''' This function has a big chunk of options and the last year was almost implemented by Kai despite of the fact that he could not finally integrate it into Octave . His approach was interfacing Octave with ITSOL/ZITSOL libraries but in the end there were some issues with that direction:
:#ILUTP algorithm did not work for him
:#ILUTP algorithm did not work for him
:#He had to patch the library to get things work, not nice for integration.
:#He had to patch the library to get things work. Not nice for achieve integration.
:#modified versions of algorithms ("milu" option) were not implemented in the libraries
:#modified versions of algorithms ("milu" option) were not implemented in the libraries
:#That "ugly" scenario lead to finally not being able to include ITSOL as a dependency with Octave. Bottom line, the integration of the function with the development\n repository could not be achieved.
:#That "ugly" scenario lead to finally not being able to include ITSOL as a dependency with Octave. Bottom line, the integration of the function with the development\n repository could not be achieved.
::I have been in contact with Kai by mail and agrees that writing from scratch all the functions needed as oct-files (ILUTP, ILU0, ILUC and ILUT) would be a valid way to go. This way no dependencies are needed to be added and the overhead of translating the data from Octave to ITSOL and vice verse is eliminated. Algorithms will be taken from Yousef Saad's  book "Iterative methods for sparse linear systems Ed. 2". Moreover, I can use some of the code that Kai wrote, mostly the tests, documentation and the m-file "ilu.m" that glue together all the functions. ITSOL source code is also a good place to look for some help.
::I have been in contact with Kai by mail and agrees that writing from scratch all the functions needed as oct-files (ILUTP, ILU0, ILUC and ILUT) would be a harder but safer way to go if integration want to be achieved. This way no dependencies are needed to be added and the overhead of translating the data from Octave to ITSOL and vice verse is eliminated. Algorithms will be taken from Yousef Saad's  book "Iterative methods for sparse linear systems Ed. 2". Moreover, I can use some of the code that Kai wrote, mostly the tests, documentation and the m-file "ilu.m" that glue together all the functions. ITSOL source code is also a good place to look for some help.
::I have implemented the ILU0 algorithm so far and benchmarked it against Matlab and Kai's last GsOC version(using ITSOL). The performance is great. You can check the code and see a table with the execution times in a blog I have created for the project([http://edu159-gsoc2014.blogspot.com.es/2014/03/ilu0-implementation.html link])
::I have implemented the ILU0 algorithm so far and benchmarked it against Matlab and Kai's last GsOC version(using ITSOL). The performance is great. You can check the code and see a table with the execution times in a blog I have created for the project([http://edu159-gsoc2014.blogspot.com.es/2014/03/ilu0-implementation.html link])


:*'''ichol:''' In this case things should be easier. Kai  implemented the functions related with ichol from Fortran prototypes and they work as exptected. It would be only necessary to code the complex version and the modified version of the algorithms. There is one issue here with licenses I did not know at first and Kai pointed me out (see [http://edu159-gsoc2014.blogspot.com.es/2014/03/introducing-myself.html#bc_0_1B here]). It should be solved.
:*'''ichol:''' In this case things should be easier at first glance. Kai  implemented the functions related with ichol from Fortran prototypes and they work as expected. In theory would be only necessary to code the complex versions and the modified versions of the algorithms. On the other hand, there is an issue here with licenses I did not know at first and Kai pointed me out (see [http://edu159-gsoc2014.blogspot.com.es/2014/03/introducing-myself.html#bc_0_1B here]). Authors should be contact in order to ask for a permission, but if they are not in favor of giving to us then another strategy will be need to be set.


:*'''sprand/sprandn:'''I have already sent a [http://savannah.gnu.org/bugs/?41839 patch] for those functions that IMHO works, but it suffers from some performance issues for large matrices. Should be revisited by someone that really knows about that. I mailed Rik who appeared as author of the function and has told me that in a few weeks he maybe be able to revise the algorithm. So in the meanwhile I will focus on other functions.


:*'''sprandsym:'''That function may be implemented following the strategy used in sprand, but I need to analyze closer.
:'''->'''I think I have a clear road map of what and how I want to do the project but I don't know for sure if it will be enough for the GSoC period. There are other functions that I would like to implement if it would be necessary like '''lsqr''' and '''minres''', both highly related with ichol and ilu. I have already done some search and found that this website [http://www.stanford.edu/group/SOL/software/lsqr/ lsqr] [http://www.stanford.edu/group/SOL/software/minres/ minres]. The website is from the people that wrote the papers given as references in Matlab documentation. In the website there are several codes that can be used. I have mailed professor Michael Saunders about adapting them into Octave versions and he answered me that I am welcome to do while I respect the license (CPL or BSD licenses). He claimed that they are very unrestrictive but I've been told that they are not compatible with GPL3. I will need some insights about that if I happen to have time for implementing them.
 
:*'''minres & lsqr:'''With the implementation of those ones I need a bit of guidance. I dont know if they must be implemented as m-scripts or in c++. I would say that they way to go is m-scripting them as ''gmres'' is implemented this way, and they are cousins. Anyway I found that this website are the place to look [http://www.stanford.edu/group/SOL/software/lsqr/ lsqr] [http://www.stanford.edu/group/SOL/software/minres/ minres]. The website is from the people that wrote the papers given as references in Matlab documentation. In the website there are several codes that can be used. I have mailed professor Michael Saunders about adapting them into Octave versions and he answered me that I am welcome to do while I respect the license (CPL or BSD licenses). He claimed that they are very unrestrictive but I've been told that they are not compatible with GPL3. I will need some insights about that.
 
 
:'''->'''I think I have a clear road map of what I want to do but I don't know for sure if it will be enough for the GSoC period. There are other functions that I would like to implement if it would be necessary. Let me know what do you think about.


*'''Estimated timeline:'''
*'''Estimated timeline:'''


:*'''FIRST PERIOD:'''  
:*'''FIRST PERIOD:'''  
::'''19  May:'''  Start implementing ilu related functions. In the order ILUT, ILUC , ILUTP.
::'''19  May:'''  Start implementing ilu related functions. In that order ILUT, ILUC , ILUTP.
::'''15  June:'''  Write ILUT, ILUC, ILUTP automated tests, documentation and benchmarking.
::'''15  June:'''  Write ILUT, ILUC, ILUTP automated tests, documentation and benchmarking.
::'''23  June:'''  '''(Millstone 1)''' ilu function is fully functional. Start coding ichol related functions (by this time license issues I mentioned should be resolved and a solid strategy should be set)
::'''23  June:'''  '''(Millstone 1)''' ilu function is fully functional. Start coding ichol related functions (by this time license issues I mentioned should be resolved and a solid strategy should be set)
Line 132: Line 125:
::'''5  August:'''  lsqr and minres implemented and tested. Start coding sprandsym and tweaking sprand/sprandn (maybe at this point they are already tweaked)
::'''5  August:'''  lsqr and minres implemented and tested. Start coding sprandsym and tweaking sprand/sprandn (maybe at this point they are already tweaked)
::'''13 August:'''  '''(Millstone 3)''' all the sp* functions are implemented
::'''13 August:'''  '''(Millstone 3)''' all the sp* functions are implemented
::'''13-18 August:'''  Buffer days for any unexpected situation or minor change that should be done.
::'''13-18 August:'''  Buffer days for any unexpected situation or minor changes that should be done.


'''Note:''' I set schedule starting on May 19th but I would like to start coding since I know I am selected (22 April), so maybe goals are would be reached before stated above. So that dates should be taken as high limits. In June I have scheduled 3 exams that still not have fixed dates. I am not worried about them since I have a lot of time for studying.
'''Note:''' I set schedule starting on May 19th but I would like to start coding since I know I am selected (22 April), so maybe goals are would be reached before stated above. So that dates should be taken as high limits. In June I have scheduled 3 exams that still not have fixed dates. I am not worried about them since I have a lot of time for studying.
77

edits

Navigation menu