Documentation : Introduction to Sparse Matrices in Scilab

Documentation : Introduction to Sparse Matrices in Scilab Commit Details

Date:2011-09-28 15:35:21 (6 years 9 months ago)
Author:Michael Baudin
Commit:12
Parents: 11
Message: * Merged "Solving Poisson PDE with Sparse Matrices" from wiki.
Changes:
A/en_US/comparisonSolvers.png
A/en_US/plotSolutionPoisson.png
A/en_US/PoissonSparsityPattern.png
M/en_US/scisparse.tex
M/changelog.txt
M/en_US/scilab.sparse.bib
M/en_US/scisparse-so.tex

File differences

changelog.txt
11
22
3
4
5
36
47
58
changelog of the Documentation : Introduction To Sparse Matrices in Scilab
docscisparse (not released yet)
* Merged "Solving Poisson PDE with Sparse Matrices" from wiki.
docscisparse (0.3)
* Updated overview.
en_US/scilab.sparse.bib
1
2
3
4
5
6
17
28
39
......
4551
4652
4753
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
% Copyright (C) 2008-2011 - Consortium Scilab - Digiteo - Michael Baudin
%
% This file must be used under the terms of the
% Creative Commons Attribution-ShareAlike 3.0 Unported License :
% http://creativecommons.org/licenses/by-sa/3.0/
@misc{ wiki:sparsematrix,
author = "Wikipedia",
title = "Sparse matrix --- Wikipedia{,} The Free Encyclopedia",
institution = {INRIA},
}
@UNPUBLISHED{wikiPoissonPDE,
author = {Michael Baudin, The Scilab Consortium},
year = {2011},
title = {Solving Poisson PDE with Sparse Matrices},
note = {\url{http://wiki.scilab.org}}
}
@UNPUBLISHED{Sharmar2010,
author = {Neeraj Sharma and Matthias K. Gobbert},
year = {2010},
title = {A Comparative Evaluation Of Matlab, Octave, Freemat, And Scilab For Research And Teaching},
note = {\url{http://userpages.umbc.edu/~gobbert/papers/SharmaGobbertTR2010.pdf}}
}
@UNPUBLISHED{Basile1989,
author = {Fran\c{c}ois Delebecque and Carlos Klimann and Serge Steer},
year = {1989},
publisher = {INRIA},
title = {Basile, un syst? de CAO pour l'automatique, version 3.0 : guide d'utilisation}
}
@UNPUBLISHED{Pincon2004,
author = {Bruno Pincon and Karim Ramdani},
year = {2004},
publisher = {IEEE International Symposium on Computer Aided Control Systems Design},
title = {Scilab tools for PDE : Application to time-reversal},
note = {\url{http://www.iecn.u-nancy.fr/~pincon/scilab/expose_taiwan.pdf}}
}
@UNPUBLISHED{BaudinProgSci2011,
author = {Michael Baudin, Consortium Scilab - DIGITEO},
year = {2011},
title = {Programming in Scilab},
note = {\url{http://forge.scilab.org/index.php/p/docprogscilab/downloads/}}
}
en_US/plotSolutionPoisson.png
en_US/PoissonSparsityPattern.png
en_US/scisparse-so.tex
1
1
22
33
44
......
1212
1313
1414
15
16
15
1716
1817
1918
% Copyright (C) 2008-2010 - Consortium Scilab - Digiteo - Michael Baudin
% Copyright (C) 2008-2011 - Consortium Scilab - Digiteo - Michael Baudin
%
% This file must be used under the terms of the
% Creative Commons Attribution-ShareAlike 3.0 Unported License :
\title{Introduction to Sparse Matrices In Scilab}
\date{Version 0.3 \\
March 2011}
\date{September 2011}
\author{Michael Baudin}
\maketitle
en_US/comparisonSolvers.png
en_US/scisparse.tex
685685
686686
687687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Solving Poisson PDE with Sparse Matrices}
In this section, we present the resolution of the Poisson Partial Differential Equation
in Scilab with sparse matrices.
We show that Scilab 5 can solve in a few seconds sparse linear systems of
equations with as many as 250 000 unknowns because Scilab only store nonzero entries.
The computations are based on the Scibench module, a toolbox which provides
a collection of benchmarks for Scilab.
This section was first published at \cite{wikiPoissonPDE}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Introduction}
Sharma and Gobbert analyzed the performance of Scilab for the resolution of
sparse linear systems of equations associated with the Poisson equation \cite{Sharmar2010}.
In this document, we try to reproduce their experiments.
We consider the Poisson problem with homogeneous Dirichlet boundary
conditions and are interested in the numerical solution based on
finite differences.
We consider the 2 dimensional problem Partial Differential Equation:
$$\begin{array}{rlll}
- \Delta u &=& f &\textrm{ in the domain,} \\
u &=& 0 &\textrm{ on the frontier.}
\end{array}$$
where the two dimensionnal Laplace operator is
$$
\Delta u = \frac{\partial^2 u}{dx^2} + \frac{\partial^2 u}{dy^2}
$$
We consider the domain $0 \leq x \leq 1$, $0 \leq y \leq 1$.
The function f is defined by
$$
f(x, y) = -2\pi^2 cos(2\pi x) sin^2(\pi y) - 2\pi^2 sin^2(\pi x) cos(2\pi y)
$$
The solution is
$$u(x, y) = sin^2(\pi x) sin^2(\pi y)$$
We use a second order finite difference approximation of
the Laplace operator based on a grid of N-by-N points.
Sparse matrices can be managed in Scilab since 1989 \cite{Basile1989}.
In Scilab 5.0 (i.e. in 2008), the UMFPACK module was added.
The Scibench external module:
\begin{center}
\url{http://atoms.scilab.org/toolboxes/scibench}
\end{center}
provides a collection of benchmark scripts to measure the performance of Scilab.
For example, it contains benchmarks for the dense matrix-matrix product,
the dense backslash operator, the Cholesky decomposition or 2D Lattice Boltzmann simulations.
The version 0.6 includes benchmarks for sparse matrices,
based on the Poisson equation.
The performance presented in this document are measured with Scilab 5.3.2 on
Windows XP with a 4GB computer using Intel Xeon E5410 4*2.33 GHz processors.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The sparse matrix}
The \scifun{scibench\_poissonA(n)} statement creates a sparse matrix equation
associated with n cells in the X coordinate and n cells in the Y coordinate.
Before calling this session, we call the stacksize function in order to let
Scilab allocate as much memory as possible.
Then we call the \scifun{PlotSparse} function to plot the sparsity pattern of the matrix.
\lstset{language=scilabscript}
\begin{lstlisting}
stacksize("max");
A = scibench_poissonA(50);
PlotSparse(A)
\end{lstlisting}
The previous script produces the plot in the figure \ref{fig-sparsityPoisson}.
\begin{figure}
\begin{center}
\includegraphics[width=10cm]{PoissonSparsityPattern}
\end{center}
\caption{Sparsity pattern of the Poisson matrix.}
\label{fig-sparsityPoisson}
\end{figure}
We emphasize that the previous matrix is a $n^2$-by-$n^2$ sparse matrix.
Even for moderate values of n, this creates huge matrices.
Fortunately, only nonzero entries are stored, so that Scilab
has no problem to store it, provided that the nonzero entries can be stored in the memory.
\lstset{language=scilabscript}
\begin{lstlisting}
-->size(A)
ans =
2500. 2500.
\end{lstlisting}
The Kronecker operator is used, so that the computation of the matrix is vectorized.
To edit the code, we just run the following code.
\lstset{language=scilabscript}
\begin{lstlisting}
-->edit scibench_poissonA
\end{lstlisting}
At the core of the algorithm, we find the statement
\lstset{language=scilabscript}
\begin{lstlisting}
A = I .*. T + T .*. I
\end{lstlisting}
where T is a sparse matrix and I is the sparse n-by-n identity matrix.
Hence, creating the whole matrix is done with only one statement.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Poisson Solver}
The \scifun{scibench\_poisson} function solves the 2D Poisson equation.
Its calling sequence is
\lstset{language=scilabscript}
\begin{lstlisting}
scibench_poisson ( N , plotgraph , verbose , solver )
\end{lstlisting}
where \scivar{N} is the number of cells, \scivar{plotgraph} is a boolean to plot the graphics,
\scivar{verbose} is a boolean to print messages and solver is a function
which solves the linear equation \scivar{A*x=b}.
The solver argument is designed so that we can customize the
linear equation solver which we want to use.
For example, if we want to use the sparse backslash operator,
all we have to do is to create the \scivar{mysolverBackslash} function as below.
\lstset{language=scilabscript}
\begin{lstlisting}
function u=mysolverBackslash(N, b)
A = scibench_poissonA(N);
u = A\b;
endfunction
\end{lstlisting}
The following script solves the Poisson equation with N = 50.
\lstset{language=scilabscript}
\begin{lstlisting}
scf();
scibench_poisson(50, %t , %t , mysolverBackslash );
\end{lstlisting}
The previous script produces the following output, where \scivar{h} is
the dimensionnal spacee step and enorminf is the value of the
infinite norm of the error.
\lstset{language=scilabscript}
\begin{lstlisting}
->scibench_poisson(50, %t , %t , mysolverBackslash );
N = 50
h = 1.9607843137254902e-002
h^2 = 3.8446751249519417e-004
enorminf = 1.2634082165868810e-003
C = enorminf / h^2 = 3.2861247713424775e+000
wall clock time = 0.15 seconds
\end{lstlisting}
The previous script also produces the plot in the
figure \ref{fig-poissonapproxsol}.
\begin{figure}
\begin{center}
\includegraphics[width=10cm]{plotSolutionPoisson}
\end{center}
\caption{Approximate solution and numerical error of the Poisson equation.}
\label{fig-poissonapproxsol}
\end{figure}
It is then easy to use the pcg function built in Scilab, which uses a
pre-conditionned conjugate gradient algorithm.
We use the \scifun{scibench\_poissonAu} function, which
computes the \scivar{A*u} product without actually storing the matrix A.
\lstset{language=scilabscript}
\begin{lstlisting}
function u=mysolverPCG(N, b)
tol = 0.000001;
maxit = 9999;
u = zeros(N^2,1);
[u,flag,iter,res] = ..
pcg(scibench_poissonAu,b,tol,maxit,[],[],u);
endfunction
scf();
[timesec,enorminf,h] = ..
scibench_poisson(50, %f , %t , mysolverPCG );
\end{lstlisting}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The benchmark}
Based on the scibench module, it is easy to compare various sparse
linear equation solvers in Scilab.
We compared the following functions:
\begin{itemize}
\item sparse backslash (which internally use a sparse LU decomposition),
\item \scifun{pcg} function,
\item \scifun{UMPFACK} module,
\item the \scifun{TAUCS} module.
\end{itemize}
Both the UMFPACK and TAUCS modules were created by Bruno Pincon \cite{Pincon2004}.
In order to use the UMFPACK module, we created the
following \scifun{mysolverUMF} function which solves the A*u=b equation.
\lstset{language=scilabscript}
\begin{lstlisting}
function u = mysolverUMF(N,b)
A = scibench_poissonA(N);
humf = umf_lufact(A);
u = umf_lusolve(humf,b)
umf_ludel(humf)
endfunction
\end{lstlisting}
We also created the following wrapper for the TAUCS module.
\lstset{language=scilabscript}
\begin{lstlisting}
function u = mysolverTAUCS(N,b)
A = scibench_poissonA(N);
hchol = taucs_chfact(A);
u = taucs_chsolve(hchol,b)
taucs_chdel(hchol)
endfunction
\end{lstlisting}
We were unable to use the TAUCS solver, which makes Scilab unstable in this case.
This problem was reported in the following bug report:
\begin{center}
\url{http://bugzilla.scilab.org/show_bug.cgi?id=8824}
\end{center}
It is straightforward to created increasingly large matrices and
to measure the time required to solve the Poisson equation.
The script is provided within the demos of the scibench module.
The plot in the figure \ref{fig-poissoncomparison} compares the various solvers.
\begin{figure}
\begin{center}
\includegraphics[width=15cm]{comparisonSolvers}
\end{center}
\caption{Comparison of solvers for the sparse linear system of equations of the Poisson equation.}
\label{fig-poissoncomparison}
\end{figure}
It is obvious that, in this case, the UMFPACK module is much faster.
The fact that we use the pcg function without actually preconditionning
the matrix is an obvious limitation of this benchmark.
This is why we work on updating the sparse ILU preconditionners in the following Forge project:
\begin{center}
\url{http://forge.scilab.org/index.php/p/spilu/}
\end{center}
The current work is based on the former Scilin project.
This benchmark shows that we can solve really large systems of equations.
The table in the figure \ref{fig-poissbenchtab} displays the performance measures.
\begin{figure}
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
\textbf{Solver} & \textbf{N} & \textbf{Matrix Size} & \textbf{Time (s)} \\
\hline
Backslash & 50 & 2500-by-2500 & 0.15 \\
PCG & 50 & 2500-by-2500 & 0.09 \\
Backslash & 100 & 10000-by-10000 & 4.32 \\
PCG & 100 & 10000-by-10000 & 0.32 \\
Backslash & 200 & 40000-by-40000 & 88.89 \\
PCG & 200 & 40000-by-40000 & 2.03 \\
UMFPACK & 200 & 40000-by-40000 & 0.81 \\
PCG & 300 & 90000-by-90000 & 7.27 \\
UMFPACK & 300 & 90000-by-90000 & 2.35 \\
PCG & 500 & 250000-by-250000 & 44.77 \\
\hline
\end{tabular}
\end{center}
\caption{The Poisson benchmark for various size of matrices.}
\label{fig-poissbenchtab}
\end{figure}
For matrices larger than approximately 400, the UMFPACK functions
fails to solve the equation because they require more memory than
Scilab can provide to it.
\lstset{language=scilabscript}
\begin{lstlisting}
--> scibench_poisson(400, %t , %t , mysolverUMF )
!--error 999
umf_lufact: An error occurred:
symbolic factorization: not enough memory
at line 3 of function mysolverUMF called by :
at line 95 of function scibench_poisson called by :
scibench_poisson(400, %t , %t , mysolverUMF )
\end{lstlisting}
We emphasize that the actual size of the matrix does not matter.
What matters is the number of nonzero terms in the matrix.
For example, with N=500, the matrix is 250000-by-250000 but
has only 1 248 000 nonzero entries.
\lstset{language=scilabscript}
\begin{lstlisting}
-->A = scibench_poissonA ( 500 );
-->size(A)
ans =
250000. 250000.
-->nnz(A)
ans =
1248000.
\end{lstlisting}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Conclusion}
Scilab 5 can manage sparse matrices and solve partial differential
equations such as the Poisson equation for example.
Indeed, Scilab provides several sparse linear equation solvers,
including a sparse backslash operator, iterative methods (e.g. the
pre-conditionned conjugate gradient algorithm) and other direct
solvers such as the UMFPACK or TAUCS modules.
With these tools we can solve huge systems of linear equations,
because Scilab only stores the nonzero entries of these massive matrices.
The solvers may fail if the memory required to store the matrix is
beyond the capacity of Scilab, but this happens only for huge matrices.
In this case, the future Scilab 6 may help to overcome this limitation,
by removing the use of the stack which is used
by Scilab 5 (see \cite{BaudinProgSci2011} for more details on this topic).
Another limitation of Scilab is that there is currently no
preconditionner for sparse linear systems of equations.
This limitation should be removed once the \emph{spilu} module is ready for a release.

Archive Download the corresponding diff file

Revision: 12