tutorial.hpp

来自「矩阵运算源码最新版本」· HPP 代码 · 共 1,484 行 · 第 1/4 页

// Software License for MTL
// 
// Copyright (c) 2007 The Trustees of Indiana University. All rights reserved.
// Authors: Peter Gottschling and Andrew Lumsdaine
// 
// This file is part of the Matrix Template Library
// 
// See also license.mtl.txt in the distribution.

#ifndef MTL_TUTORIAL_INCLUDE
#define MTL_TUTORIAL_INCLUDE

// for references
namespace mtl {

// This file contains no source code but only documentation.

/*! \mainpage MTL4 manual

\author Peter Gottschling and Andrew Lumsdaine

Many things can be realized on a computer very elegantly and efficiently today
thanks to progress in software and programming languages.
One thing that cannot be done elegantly on a computer is computing.
At least not computing fast.

In the %Matrix Template Library 4 we aim for a natural mathematical 
notation without sacrifying performancs.
You can write an expression like x = y * z and the library will
perform the according operation: scaling a vector, multiplying a
sparse matrix with a dense vector or two sparse matrices.
Some operations like dense matrix product use tuned BLAS implementation.
In parallel, all described operations in this manual are also realized in C++
so that the library can be used without BLAS and is not limited to types
supported by BLAS.
For short, general applicability is combined with maximal available performance.
We developed new techniques to allow for:
- Unrolling of dynamicly sized data with user-define block and tile sizes;
- Combining multiple vector assignments in a single statement (and more importingly perform them in one single loop);
- Storing matrices recursively in a never-before realized generality;
- Performing operations on recursive and non-recursive matrices recursively;
- Filling compressed sparse matrices efficiently;
.
and much more.

The manual still not covers all features and techniques of the library.
But it should give you enough information to get started.

- \subpage intro 
- \subpage install 
- \subpage IDE
- \subpage tutorial  



*/

//-----------------------------------------------------------

/*! \page intro Introduction




Many things can be realized on a computer very elegantly and efficiently today
thanks to progress in software and programming languages.
One thing that cannot be done elegantly on a computer is computing.
At least not computing fast.

High performance computing (HPC) is to a large extend influenced by some
highly tuned numeric libraries.
Assume we want to multiply two matrices, i.e. calculate A = B * C.
Then we can use some libraries that run at over 90 per cent peak performance.
We only need to write something like:
\code
	int m= num_rows(A), n= num_cols(B), k= num_cols(A), 
            lda= A.get_ldim(), ldb= B.get_ldim(), ldc= C.get_ldim();
	double alpha= 1.0, beta= 1.0;
	char a_trans= 'N', b_trans= 'N';
	_dgemm(&a_trans, &b_trans, &m, &n, &k, &alpha, &A[0][0], &lda, 
	       &B[0][0], &ldb, &beta, &C[0][0], &ldc);
\endcode
No doubt, next time we call dgemm we instantly remember the exact order of the 13 arguments.
Certainly, calling the C-BLAS interface looks somewhat nicer and we can write functions
that deal with the dimensions and the orientation, like dgemm(A, B, C).
We can furthermore write a polymorphic function gemm that accordingly calls _sgemm, _dgemm
and so on.
Indead, there is a project working on this.
But is this all we want?
Why not writing A = B * C; and the library calls the according BLAS function?
What do we want to do if there is none?


Programmers working with BLAS libraries
are forced to limit themselves to the operations and types provided by these
packages.
As an example, if one likes to use single-precision floats for preconditioner
matrices--to save memory bandwidth--while the vectors are double-valued, 
one cannot use regular BLAS libraries.
In contrast, any generic library that contains a matrix vector product
can perform this operation.

And what if somebody wants to build matrices and vectors of quaternions or intervals?
Or rationals?
How to calculate on them?
Again, this is no problem with a generic library but it would take enormous implementation efforts
in Fortran or C (even more in an assembly language to squeaze out the last nano-second of run-time
(on each platform respectively)).


Mathematica and Matlab are by far more elegant than C or Fortran libraries.
And as long as one uses standard operations as matrix products they are fast
since they can use the tuned libraries.
As soon as you start programming your own computations looping over elements
of the matrices or vectors your performance won't be impressive, to say the least.

MTL4 allows you to write A = B * C and let you use BLAS internally if available.
Otherwise it provides you an implementation in C++ that is also reasonably fast (we usually
reached 60 per cent peak).


All this said, dense matrix multiplication is certainly the most benchmarked operation
on high performance computers but not really the operation that high performance computers
use the most in real applications.
The dominant part of scientific computing in HPC are simulations that are mostly 
handled with finite element methods (FEM), finite volume methods (FVM),
finite difference methods (FDM), or alike.
The numeric problems that arise from these methods are almost ever linear or non-linear
systems of equations in terms of very large sparse matrices and dense vectors.

In contrast to most other libraries we paid strong attention to sparse matrices and their
operations.
To start with, we developed an efficient method to fill the matrices and compress them
in-place, cf. \ref matrix_insertion.
This allows for matrix sizes that are close to the memory size.
It is also possible to change the compressed matrices later.


The product of sparse matrices with dense ones allows you to multiply a sparse matrix 
simultaneously with multiple vectors.
Besides cache reuse regarding the sparse matrix simple and efficient loop unrolling
could be applied. (Performance plots still pending ;-) ) 

Sparse matrices can be multiplied very fast with MTL4.
In the typical case that the number of non-zeros per row and per column is 
limited by a constant for any dimension, 
the run-time of the multiplication is linear in the number of rows or columns.
(Remark: we did not use the condition that the number of non-zeros in the matrix is proportional to 
the dimension. This condition includes the pathological case that the first matrix contains
a column vector of non-zeros and the second one a row vector of non-zeros. Then
the complexity would be quadratic.)
Such matrices usually originate from FEM/FDM/FVM discrezations of PDEs on continous domains.
Then the number of rows and columns corresponds to the number of nodes or cells in the 
discretized domain.
Sparse matrix products can be very useful in algebraic multigrid methods (AMG).

Returning to the expression A = B * C; it can be used to express every product of 
sparse and dense matrices.
The library will dispatch to the appropriate algorithm.
Moreover, the expression could also represent a matrix vector product if A and C
are column vectors (one would probably choose lower-case names though).
In fact,  x = y * z can represent four different operations:
- matrix product;
- matrix vector product;
- scalar times matrix; or
- scalar times vector.
.


There is much more to say about MTL.
Some of it you will find in the \ref tutorial, some of it still needs to be written.



Proceed to the \ref install "installation guide".

*/

//-----------------------------------------------------------


/*! \page install Installation guide

MTL4 is a pure template library and only a download of the sources
is required.

The <a href="http://www.boost.org">Boost library</a>
is used and must also be downloaded.
We used in the development and testing version 33.1 but the programs
would probably compile with earlier versions, too.
 The parts of boost used in MTL4 do not need
to be compiled but only included.

If you want to run the test programs, you need the build system
<a href="http://www.scons.org">scons</a>.
It is easy to install and takes only a few minutes.
The scons-based build of MTL4 uses the environment variables 
<tt>MTL_BOOST_ROOT</tt> to locate the MTL directory
and <tt>BOOST_ROOT</tt> to locate the Boost directory.

If you compile MTL4 with VS2005 or its free express version
you need to install the SDK (some boost files access it).
Please make sure that the compiler is in the path.
Then scons will find it.
Additionally, you have to tell the compiler where the header files and
the libraries of VC and the SDK are located, i.e. declare the 
environment variables LIB and INCLUDE. For instance:\n
<tt>LIB=c:/Program Files/Microsoft Visual Studio 8/vc/lib;c:/Program Files/MicrosoftVisual Studio 8/vc/platformsdk/lib</tt>\n
<tt>INCLUDE=c:/Program Files/Microsoft Visual Studio 8/VC/include;c:/Program Files/Microsoft Visual Studio 8/VC/PlatformSDK/Include</tt>\n
On some machines the compiler still did not find the files. For that reason the
paths within these two variables are incorporated into the command line by our scons script.



To execute the test programs go in MTL4's test directory
libs/numeric/mtl/test and type:\n
<tt>scons -D . check=1</tt>\n
If the building finishes all tests were passed.
The building can be considerably speed up, esp. on multi-core processors,
when scons is used with multiple processes.
For instance, to run the tests with four processes (which works quite
well on two processors) type:\n
<tt>scons -Dj 4 . check=1</tt>\n
The output will be quite chaotic but, again, when the building finishes
all tests are passed.

Similarly, the example programs can be compiled.
Go in directory libs/numeric/mtl/examples and type:\n
<tt>scons -D .</tt>\n
For the sake of simplicity, there are no checks in the examples (nevertheless an exceptions
thrown in the examples help to fix a bug).

To compile (and test) all programs you can run scons in the main directory (then you do not
need the -D option and the dot) or in any directory of the tree if you use -D and omit the dot.
You can also compile single files if you specify the name of the executable (including .exe on
windows).

If you want to use BLAS, you need to define the macro <tt>MTL_HAS_BLAS</tt>,
e.g., by compiling your programs with 
<tt>-DMTL_HAS_BLAS</tt>, and link the appropriate libraries.
Alternatively, you can use MTL4's build system 
with the flag <tt>with-blas=1</tt> that will
check if GotoBlas, ACML, or ATLAS is installed on your system
(thanks to Torsten Hoefler who wrote the tests in scons).
If scons does not find your BLAS library you can specify additional
flags, see\n
<tt>scons -h</tt>\n
for details.

If you wish to generate the documentation locally on your system
you need <a href="http://www.doxygen.org">doxygen</a>.
When it is installed type <tt>doxygen</tt> in the main directory and
the documentation will be written to libs/numeric/mtl/doc.

Resuming, for MTL4 you need to:
- Include the MTL path;
- Include the boost path;
- Optionally install scons;
- Optionally install a BLAS library; and
- Optionally install doxygen.

\section supported_compilers Supported compilers

The %Matrix Template Library is written in compliance with the C++ standard
and should be compilable with every compiler compliant with the standard.
It has been tested (and passed) with the following compilers and architectures:
- Linux
  - g++ 4.0.1
  - g++ 4.1.1
  - g++ 4.1.2
  - icc 9.0
- Macintosh
  - g++ 4.0.1
- Windows
  - VC 8.0 from Visual Studio 2005

More compilers will be tested in the future.

Compilers that are not standard-compliant (e.g. VC 6.0 from VS 2003) are not subject to support.


Proceed to the \ref IDE.  

*/


//-----------------------------------------------------------


//-----------------------------------------------------------
/*! \page IDE IDE

Some short descriptions how to use MTL4 with different IDE's.

- Eclipse
  - Windows
    - \subpage winxp_eclipse32_gcc323
  - Linux
- MS Visual Studio
  - Visual studio 2005 was successfully used for debugging single files but until now nobody compiled the entire test suite (to our knowledge). 
- WingIDE
  - WingIDE is said to support scons and their is a how-to to this subject. But again, it is not yet tried.
.

Experiences with IDEs are welcome and we would be happy to provide more help in the future.

Proceed to \ref tutorial "the tutorial".  

*/

//-----------------------------------------------------------
/*! \page winxp_eclipse32_gcc323 WinXP / Eclipse-3.2 CDT-3.1 / gcc-3

You should have some basic experience with Eclipse. So I won't explain
each step for downloading and installing Eclipse/CDT. 

Some informations about the used systems:
-# OS: WinXP SP2 with all updates (it's my business notebook, so 
   I can't do something against the updates  :-(   )
-# Compiler: MinGW32 with gcc-3.2.3
-# Eclipse-3.2
-# CDT-3.1.2

Some informations about the installation path:
-# MinGW32: is installed in c:/MinGW
-# Eclipse: is installed in c:/Programme/eclipse
-# CDT-3.1.2: will be installed automatically in the eclipse directory
-# MTL4/Boost: are installed in c:/cppLibs/mtl4 and in c:/cppLibs/boost_1_34_1

Now let's starting Eclipse. If Eclipse is started, change to the c++ perspective.
If this is the first time you can do it under:\n
<tt>Window/Open Persepctive/Other</tt>\n
Now chose \c c++ and the view will get a new look!

To show the configuration we will create a new project. Chose\n
<tt>File/New/Project.../Managed Make C++ Project</tt>\n
This will open a new dialog. Enter <tt>vector1</tt> as project name. I will change
the \c Location to <tt>u:/programming/vector1</tt>. To do this, click on the
check box, now you can push the \c Browse button. The next dialog will open. Chose
a path and in my case, the directory \c vector1 doesn't exist. So I have to
push the button <tt>new directory</tt> and enter the directory name \c vector1.
Now click \c Next.

Click \c Finish on the new dialog. The new project will be created and you can
see it on the left side in the \c Navigator or in the <tt>C/C++ Projects</tt> view.

Now let's copy the \c vector1.cpp of the mtl4 example in the new project directory.
Press \c F5 to update the C++ perspective. Maybe you have to push more than only once.
Java isn't so fast :-)\n
Now you can see the file \c vector1.cpp in the <tt>C/C++ Projects</tt> view.

Before we start with configuring this project, let's check your installation of
MinGW. Enter at the command prompt <tt>gcc --version</tt>. Now something similar
like <tt>gcc (GCC) 3.2.3 (mingw special....)</tt> should appear. Be sure that you 
don't have a second compiler in your path. Please don't install the MSYS package.
This will cause some problems during the linking process. If you get here an error,
please first fix this! Check your path variable and so on. Like the MSYS CYGWIN 
will also cause some problems. Remove the path entry, if you have installed CYGWIN!

Now mark with one left click your project in Eclipse. Than one right click to open 
a context menu. Go down to \c Properties and click again. <tt>Properties for vector1
</tt> dialog appears. Click on <tt>C/C++ Build</tt>. In this section, we will find 
all the necessaries properties we have to configure.

In <tt>Active configuration</tt> you can read \c Debug. For this simple example,
change it to \c Release.

Now in <tt>Configuration Settings / Tool Settings</tt> click on 
<tt>GCC C++ Compiler / Directories</tt>. Here we have to include the
directories of mtl4 and the boost library. We can do it with a click
on the icon with the green cross. In the new dialog, click on