My little talk on the OctConf 2013

The material of my little talk is on the OctConf 2013 available from here:

https://drive.google.com/folderview?id=0B4V9W1l15-xMOU5fTHJ6ZzlEVXc&usp=sharing

Getting ITSOL to work

At the moment I'm writing an interface for GNU/Octave, to make use of the ITSOL library. This post should be a collection of information how to get this library on your machine.
As far as I figured out, there are is only an outdated package maintained in the Debian repository for ITSOL, so one has to build the library and copy the necessary files to the file system.

Build the ITSOL-library from source

1. Get the source tar-archive
2. Extract the archive: tar -xvf ITSOL_2.tar.gz
3. Get my patch
4. Apply the patch to the extracted archive:
• cd ITSOL_2
• patch -p1 < itsol.patch
5. Build the library using: make
• Now the shared and static library are created in ITSOL_2/LIB
6. Copy the header files from ITSOL_2/INC to /usr/include/itsol (root rights may be required)
7. Copy the two libraries from ITSOL_2/LIB to /usr/lib
8. Make symbolic links
• ln -s libitsol.so.1.0.0 libitsol.so.1
• ln -s libitsol.so.1 libitsol.so

---

Hint for steps 6+7: If you choose a custom location, you can build Octave later using the configure options:

• --with-itsol-includedir=DIR

• --with-itsol-libdir=DIR

See configure --help for details

---

Linux

• Debian/Ubuntu: sudo apt-get install libitsol1 libitsol-dev (outdated)
• openSuse: ??
• fedora: ??
• ... : ??

Windows

• MinGW: ??
• Cygwin: ??

Mac

• ??

And then there was iluk()

Little good news for the weekend: my first interface to ITSOLs ILUK is working as desired:

>> A_sparse = spconvert([...
     1 4 2 3 3 4 2 5; % row indices
     1 1 2 3 4 4 5 5; % column indices
     1 2 3 4 5 6 7 8  % non-zero values
     ]');

>> [L,U] = iluk(A_sparse)
L =

Compressed Column Sparse (rows = 5, cols = 5, nnz = 6 [24%])

  (1, 1) ->  1
  (4, 1) ->  2
  (2, 2) ->  1
  (3, 3) ->  1
  (4, 4) ->  1
  (5, 5) ->  1

U =

Compressed Column Sparse (rows = 5, cols = 5, nnz = 7 [28%])

  (1, 1) ->  1
  (2, 2) ->  3
  (3, 3) ->  4
  (3, 4) ->  5
  (4, 4) ->  6
  (2, 5) ->  7
  (5, 5) ->  8

>> L * U - A_sparse % Should be a zero matrix
ans =

Compressed Column Sparse (rows = 5, cols = 5, nnz = 0 [0%])

Another example from MATLAB http://www.mathworks.com/help/matlab/ref/ilu.html

>> A = gallery('neumann', 1600) + speye(1600);
>> nnz(A)
ans =  7840
>> nnz(lu(A))
ans =  126402
>> [L,U] = iluk(A);
>> nnz(L+U-speye(size(A))) % This behaviour will be added to ilu.m later
ans =  7840

Now I'm very optimistic, that the ILUT and ILUC will be interfaced till the end of the next week.

Yet another repository

Thanks to Jordi, hereby I announce a new Mercurial-repository for the development of my GSoC project. It has a public web interface:

http://inversethought.com/hg/octave-kai/

Clone my whole repository:

    hg clone http://inversethought.com/hg/octave-kai/

If you have already an Octave repository and want to give my code a try. First check impact, then pull:

    hg incoming http://inversethought.com/hg/octave-kai/ -r kais-work

    hg pull http://inversethought.com/hg/octave-kai/

There follow some notes mainly for myself, how one can work with that Mercurial-repository.

See new page: http://siko1056-gsoc.blogspot.de/p/getting-my-work.html

Working with bookmarks

hg bookmark kais-work    # Create bookmark

hg update -r kais-work   # Switch to my bookmark 

hg push -B kais-work     # Make it public available

Stay up to date with recent development changes:

hg pull http://www.octave.org/hg/octave
hg merge default
hg commit -m "maint: periodic merge with Octave repository"
hg update -C tip
hg bookmark -f kais-work
hg push ssh://inverse@inversethought.com/hg/repos/octave-kai

See new page: http://siko1056-gsoc.blogspot.de/p/getting-my-work.html

A more detailed plan of action

In this post I want to summarize and update my project state and progress. First an overview:

Project timeline:

https://www.google.com/calendar/embed?src=fe9sdg54bacec0epcppj4d0i1g%40group.calendar.google.com&ctz=Europe/Berlin 

Goals for the Midterm 2013-07-29 (Monday) :

• 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

Goals for the Final Evaluation 2013-09-16 (Monday, "Suggested 'pencils down' date") :

• Implementations for IC(0) and ICT completed
• Wrapper file for MATLAB compatibility (ichol.m) finished
• Small test cases for all incomplete-factorizations
• Documentation of incomplete LU-factorization types
• Comprehensive test cases for all types of incomplete-factorization types (also  proofing compatibility to MATLAB)
• (optional) Complex version for the incomplete-factorizations

Sparse exercise: a potential interface for ITSOL or CRS-based functions

The user wants to factorize this sparse matrix

$ A = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 7 \\ 0 & 0 & 4 & 5 & 0 \\ 2 & 0 & 0 & 6 & 0 \\ 0 & 0 & 0 & 0 & 8 \\ \end{pmatrix} $

Get the matrix into Octave

Just provide a Matrix with three columns:

>> A_sparse = spconvert([...
     1 4 2 3 3 4 2 5; % row indices
     1 1 2 3 4 4 5 5; % column indices
     1 2 3 4 5 6 7 8  % non-zero values
     ]')

A_sparse =

Compressed Column Sparse (rows = 5, cols = 5, nnz = 8 [32%])

  (1, 1) ->  1
  (4, 1) ->  2
  (2, 2) ->  3
  (3, 3) ->  4
  (3, 4) ->  5
  (4, 4) ->  6
  (2, 5) ->  7
  (5, 5) ->  8

What needs to be passed to ITSOL

The approach I would favor in order to interface the ITSOL library is to factorize the transposed matrix to avoid timing problems resulting from input and output format conversion.

$ \mathbf{A} = \mathbf{L}\mathbf{U} \Leftrightarrow \mathbf{A^{T}} = \mathbf{U^{T}}\mathbf{L^{T}} $

Conversion with implicit tranposition.

Information on the Octave sparse matrix format:

• http://arxiv.org/abs/cs/0604006
• https://www.gnu.org/software/octave/doc/interpreter/Storage-of-Sparse-Matrices.html#Storage-of-Sparse-Matrices