Monday, July 29, 2013

Midterm summary

Today it is time for the midterm and to summarize what has already been done. Here is again my favorite picture to show my progress and afterwards some text.


















Goals for the Midterm:

  • Integration of ITSOL completed (iluk.cc, ilut.cc, ilutp.cc, iluc.cc), callable from Octave
  • Wrapper file for MATLAB compatibility (ilu.m)
  • Small test cases for incomplete LU-factorization, showing their correctness
  • Documentation of incomplete LU-factorization types
  • Comprehensive test cases for all types of incomplete LU-factorization types (also  proofing compatibility to MATLAB)
  • (optional) Complex version for the incomplete-factorizations
All in all I'm satisfied with the first part of this GSoC. I wrote about 2374 SLOC (rough wc -l estimate), patched two libraries and modified some config files. The major part of my work except the integration into the Octave build system can be downloaded from here to try it out without needing a development version.

Going from the bottom up in the picture, I'm not an expert, but very familiar with ITSOL and ZITSOL now. I created patches for both libraries (also included into my archive above) that one can use them on a unix-like system, but so far they are only tested on my *buntu systems. A special part of this work is, that I patched a whole ZILUC function into ZITSOL, which should be used with care. All other complex version are mainly implemented by switching the data type. For small examples this approach works at ILUC as well, but some differences where observable.

With patched libraries one can go an level up, where I created interfaces to use the most relevant function from the preconditioner libraries. For mastering this task I needed to get to know the different matrix storage formats of Octave and (Z)ITSOL and had some trouble with the matrix conversion. Building upon Wei Jins initial work I successfully interfaced ILUK, ILUT and ILUC + their complex versions. They all deliver comparable results to Matlab. Sadly the authors of (Z)ITSOL seem to be busy at this moment, so I still don't have any clue how to get ILUTP to run. This will tried to be solved in the second part of GSoC, too.

When you have an interface, it still needs to be integrated in the big Octave code base. Therefore I got familiar with the Octave build system and made all the sufficient changes, including checking for the presence of ITSOL and ZITSOL and making sure that all necessary files are build by default.

On the last level there is "only" one m-file ensuring the compatibility to MATLABs ilu-function. As one can see from the picture, I couldn't make everything green because of two reasons. First ILUTP is missing and second I cannot include an efficient MILU (modified ILU, see http://www.mathworks.de/de/help/matlab/ref/ilu.html) without changing the code of ITSOL entirely. The following two examples work in Octave and MATLAB the same, especially the last example reveals the benefit of preconditioning.

Example 1

A = gallery('neumann', 1600) + speye(1600);
setup.type = 'nofill';
nnz(A)
ans = 7840

nnz(lu(A))
ans = 126478

nnz(ilu(A,setup))
ans = 7840

Example 2

A = gallery ('wathen', 10, 10);
b = sum (A,2);
tol = 1e-8;
maxit = 50;
opts.type = 'crout';
opts.droptol = 1e-4;
[L, U] = ilu (A, opts);
x = bicg (A, b, tol, maxit, L, U);
norm(A * x - b, inf)

All written functions contain much documentation, callable with doc ilu* and comprehensive test cases, which you can try out from the archive with
test ilu
test src/iluc
test src/iluk
test src/ilut
because *.oct file and source file are in separate directories.

Besides coding, I additionally had the pleasure to join this years OctConf in Milan. I was given the opportunity to know better the community and held a short presentation about my project.

Finally I want to thank the Octave community for supporting me a lot during the initial part of my project work and I really look forward for the second part and the time after this!

No comments:

Post a Comment