<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>linbox: LinBox tutorial</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.7.4 -->
<script type="text/javascript">
function hasClass(ele,cls) {
return ele.className.match(new RegExp('(\\s|^)'+cls+'(\\s|$)'));
}
function addClass(ele,cls) {
if (!this.hasClass(ele,cls)) ele.className += " "+cls;
}
function removeClass(ele,cls) {
if (hasClass(ele,cls)) {
var reg = new RegExp('(\\s|^)'+cls+'(\\s|$)');
ele.className=ele.className.replace(reg,' ');
}
}
function toggleVisibility(linkObj) {
var base = linkObj.getAttribute('id');
var summary = document.getElementById(base + '-summary');
var content = document.getElementById(base + '-content');
var trigger = document.getElementById(base + '-trigger');
if ( hasClass(linkObj,'closed') ) {
summary.style.display = 'none';
content.style.display = 'block';
trigger.src = 'open.png';
removeClass(linkObj,'closed');
addClass(linkObj,'opened');
} else if ( hasClass(linkObj,'opened') ) {
summary.style.display = 'block';
content.style.display = 'none';
trigger.src = 'closed.png';
removeClass(linkObj,'opened');
addClass(linkObj,'closed');
}
return false;
}
</script>
<div id="top">
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">linbox</div>
</td>
</tr>
</tbody>
</table>
</div>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li class="current"><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
<li><a href="dirs.html"><span>Directories</span></a></li>
<li><a href="examples.html"><span>Examples</span></a></li>
</ul>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="index.html">LinBox Symbolic Linear Algebra Software Library.</a> </li>
</ul>
</div>
</div>
<div class="header">
<div class="headertitle">
<div class="title"><a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> tutorial </div> </div>
</div>
<div class="contents">
<div class="textblock"><p>The person requiring some exact linear algebra computation may exploit <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> at any of four general levels.</p>
<p>In order from least involved with the details to most involved, they are:</p>
<ol>
<li>
<p class="startli">Access using a <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> web server. </p>
<p>The user at this level must attend to preparation of a matrix in a suitable file format and invoking the webservice. The server itself should provide adequate documentation for this. Servers are generally available at <a href="http://www.linalg.org" target="_blank">linalg.org</a>.</p>
<p class="endli"></p>
</li>
<li>
<p class="startli">Access using compiled codes. Full programs exist in the examples directory and can be used through an interface to <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> in a general purposes system such as Maple or <a href="http://www.sagemath.org" target="_blank">SAGE</a>. </p>
<p>The user at this level must see to installation, and then attend to preparation of her matrix in a suitable file format and to the form of the program or procedure invocation. A number of programs are available in the examples directory distributed with <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> providing for rank, determinant, linear system solution, etc. The documentation of the examples module should serve for this level of access.</p>
<p class="endli"></p>
</li>
<li>
<p class="startli">Use of <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> as a programmers library for exact linear algebra functions. </p>
<p>At this level a user must do at least the following: </p>
<ol type="a">
<li>
Choose a field or ring representation and construct a specific field or ring object <code>R</code>. </li>
<li>
Choose a blackbox or matrix representation suitable to your data and construct specific matrix <code>A</code> over <code>R</code>. </li>
<li>
Call needed algorithm. The solutions directory is designed to support this by providing functions with simple problem oriented interfaces (<code><a class="el" href="group__solutions.html#gaae3c1f7fd3319410ac4fc3e4e3afdd01" title="Compute the rank of a linear transform A over a field by selected method.">rank()</a></code>, <code><a class="el" href="group__solutions.html#ga9cfcc847d3a7deac68ad6d98e0cd384f" title="Compute the determinant of A.">det()</a></code>, <code><a class="el" href="group__solutions.html#gaeb41d28dc7bebfd5a24b7642631e9817" title="Solve Ax = b, for x.">solve()</a></code>), yet allowing some user control of algorithm details. The programmer may be providing some of the parts such as an application specific blackbox matrix class. </li>
</ol>
<p class="endli"></p>
</li>
<li>
<p class="startli">Power development. </p>
<p>Again, this is use of <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> as a library, but with hands fully on the details. The programmer at this level apparently needs the best opportunities for high performance and is willing to use the more complicated internal interfaces to get it. Direct calls to functions in the algorithms directory and perhaps to related packages such as <code>FFLAS</code>, <code>FFPACK</code>, or other components are being used. The programmer working at this level of intimacy with <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> is likely to develop some components that ought to be included in future releases of <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a>. Such contributions are warmly welcomed. The online documentation system is intended primarily for the programmer at level 3. Thus documentation is not generated to the last internal detail. It is supposed that the level 4 (and 3) programmer, when studying internal details, will be best served by reading the code. It is possible, if you wish, to set <a href="http://www.doxygen.org/" target="_blank">doxygen</a> parameters so as to have a documentation listing for every class and function. Good luck separating wheat from chaff in that case.</p>
<p class="endli"></p>
</li>
</ol>
<p>In this tutorial we will discuss a simple application at level 3, the design of a program to compute the determinant of a sparse matrix over <img class="formulaInl" alt="$\mathbf{GF}(101)$" src="form_75.png"/>. The programmer has 3 major issues: field, matrix, algorithm.</p>
<p>The basic algorithm choice is between blackbox and elimination algorithms. If our matrix is <code>A</code>, then the algorithm call may look like </p>
<div class="fragment"><pre class="fragment"><a class="code" href="group__solutions.html#ga9cfcc847d3a7deac68ad6d98e0cd384f" title="Compute the determinant of A.">det</a>(d, A, Method::Blackbox());
<span class="comment">//or</span>
<a class="code" href="group__solutions.html#ga9cfcc847d3a7deac68ad6d98e0cd384f" title="Compute the determinant of A.">det</a>(d, A, Method::Elimination());
</pre></div><p> To have access to this determinant function just <code>#include <<a class="el" href="det_8h.html" title="NO DOC.">linbox/solutions/det.h</a>></code>.</p>
<p>The larger and sparser the matrix the more likely that the blackbox algorithm is fastest. Hybrids are under development to help make this choice, and even to make it at run time adaptively. The last argument to the solutions functions is a method object which specifies the algorithm to be used. In each case there is a default, so this argument is optional. Also, some method objects may be constructed so as to convey more detail about the algorithm to use. For example it may help to promise that the matrix is nonsingular or symmetric or to request a particular algorithm variant. The blackbox algorithm based fundamentally on Wiedemann's approach is specified by <code>Method::Wiedemann</code>, see <code><a class="el" href="methods_8h.html" title="NO DOC.">solutions/methods.h</a></code> for more details. Specification of a blocked blackbox algorithm may be advantageous (in the future). Elimination is likely fastest if the matrix is not extremely sparse or not large or not subject to rapid fill-in.</p>
<p>Of course, first we must construct the matrix and field. For the field, you must first choose the class (representation type) of field and then instantiate your specific field.</p>
<div class="fragment"><pre class="fragment"><span class="preprocessor">#include <<a class="code" href="field_2modular_8h.html" title="A Modular field is a representations of Z/mZ.">linbox/field/modular.h</a>></span>
<span class="keyword">typedef</span> Modular<short> <a class="code" href="class_lin_box_1_1_modular_3_01uint32__t_01_4.html" title="Specialization of class Modular for uint32_t element type.">Field</a>;
Field F(101);
</pre></div><p>It is a good idea to use a <code>typedef</code>, making it easy to change representations later. The <a class="el" href="group__modular.html">Modular</a> field representations are LinBox's own and contain some useful optimizations. Another possibility is use of <a href="http://shoup.net/ntl/" target="_blank">NTL</a>'s <code>NTL::ZZ_p</code> class. The <a class="el" href="namespace_lin_box.html" title="Namespace in which all linbox code resides.">LinBox</a> wrapper of that, called <code><a class="el" href="struct_lin_box_1_1_n_t_l___z_z__p.html" title="Wrapper of zz_p from NTL.">LinBox::NTL_ZZ_p</a></code> is found in <code><a class="el" href="ntl-_z_z__p_8h.html" title="NO DOC.">field/ntl-ZZ_p.h</a></code>. Or use a <a href="http://ljk.imag.fr/CASYS/LOGICIELS/givaro/" target="_blank">Givaro</a> table based representation, <code><a class="el" href="class_lin_box_1_1_givaro_gfq.html" title="Wrapper of Givaro's GFqDom<int32_t> class.">LinBox::GivaroGfq</a></code> in <code><a class="el" href="givaro-gfq_8h.html">field/givaro-gfq.h</a></code> ...and there are many other options. The program <code>tests/test-fields.C</code> will provide some timing data on the basic functions of each representation. In LinBox, a <code>Field</code> class and the class representing the field entries are distinct types. The field object owns the arithmetic operations, whereas the entry objects may be of a primitive type such as <code>short</code>, <code>int</code>, <code>double</code>. Each field class <code>Fld</code> has the embedded class <code>Fld::Element</code> for it's elements.</p>
<div class="fragment"><pre class="fragment">Field::Element a, b, c;
F.init(a, 2); F.init(b, 3);
F.mul(c, a, b); <span class="comment">// c <- a*b</span>
F.write(cout, c);
</pre></div><p>You have seen that the field representations are in subdirectory <code>linbox/field</code>. Similarly the matrix representations are in <code>linbox/blackbox</code>. All of these are are suitable for blackbox algorithms. Only those deriving from representations in <code>linbox/matrix</code> are suitable for elimination. For a sparse matrix, <code><a class="el" href="class_lin_box_1_1_triples_b_b.html" title="wrapper for NAG Sparse Matrix format.">LinBox::TriplesBB</a></code> is a good representation choice if a blackbox algorithm is to be used. For a <img class="formulaInl" alt="$\{0,1\}-$" src="form_76.png"/>incidence matrix, the class <code><a class="el" href="class_lin_box_1_1_zero_one.html" title="Time and space efficient representation of sparse {0,1}-matrices.">LinBox::ZeroOne</a></code> will be more economical of space and time. On the other hand, if elimination is to be used, those will not serve at all, but <code><a class="el" href="class_lin_box_1_1_sparse_matrix.html" title="vector of sparse rows.">LinBox::SparseMatrix</a></code>, which allows internal modification, will do the trick. The ordinary matrix representation is <code><a class="el" href="class_lin_box_1_1_dense_matrix.html" title="Blackbox interface to dense matrix representation.">LinBox::DenseMatrix</a></code>. If your matrix structure allows you to compute matrix-vector products in a way faster than these classes provide, you can gain by defining your own matrix class adhering to the <a class="el" href="group__blackbox.html">blackbox</a> interface. The main components of the blackbox interface are member functions <code>apply()</code> and <code>applyTranspose()</code> functions. <code>A.apply(y, x)</code> performs <img class="formulaInl" alt="$y \gets Ax$" src="form_73.png"/>.</p>
<p>Then there is the question of initializing matrix entries. Two basic approaches are illustrated here.</p>
<div class="fragment"><pre class="fragment">TriplesBB A;
A.read(<span class="stringliteral">"triples-file"</span>); <span class="comment">// initialize A from data in file (including shape).</span>
</pre></div><p>Or a program can add entries to a sparse or dense matrix one by one using the <code>setEntry</code> function.</p>
<div class="fragment"><pre class="fragment">SparseMatrix B(100, 200); <span class="comment">// 100 by 200 zero matrix (so far).</span>
<span class="keywordflow">for</span> ( ... )
{
Field::Element v;
F.init(v, ...);
B.setEntry(i, j, v); <span class="comment">// put nonzero v in i,j position.</span>
}
</pre></div><p>Putting it all together, we may have a program looking like this. </p>
<div class="fragment"><pre class="fragment"><span class="preprocessor">#include <<a class="code" href="field_2modular_8h.html" title="A Modular field is a representations of Z/mZ.">linbox/field/modular.h</a>></span>
<span class="preprocessor">#include <<a class="code" href="blackbox_2dense_8h.html" title="NO DOC.">linbox/blackbox/dense.h</a>></span>
<span class="preprocessor">#include <<a class="code" href="det_8h.html" title="NO DOC.">linbox/solutions/det.h</a>></span>
<span class="keyword">using namespace </span>LinBox;
main()
{
<span class="keyword">typedef</span> <a class="code" href="class_lin_box_1_1_modular_3_01double_01_4.html" title="Standard representation of .">Modular<double></a> Field;
<span class="keyword">typedef</span> <a class="code" href="class_lin_box_1_1_dense_matrix.html">DenseMatrix<Field></a> <a class="code" href="class_lin_box_1_1_zero_one.html">Matrix</a>;
Field F(65521);
Matrix A; A.<a class="code" href="class_lin_box_1_1_zero_one.html#a7f1e7ece6c12a9a3feb091f90c7c9ac1" title="Read the matrix from a stream in the JGD's SMS format.">read</a>(<span class="stringliteral">"datafile"</span>);
Field::Element d;
<a class="code" href="group__solutions.html#ga9cfcc847d3a7deac68ad6d98e0cd384f" title="Compute the determinant of A.">det</a>(d, A, blasElimination);
F.write(cout << <span class="stringliteral">"the determinant is "</span>, d) << endl;
}
</pre></div><p>This tutorial should continue with a discussion of compilation issues, but it doesn't. Something useful may be learned from examining the Makefile.am in the examples directory. </p>
</div></div>
<hr class="footer"/><address class="footer"><small>Generated on Tue Aug 30 2011 for linbox by 
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.4 </small></address>
</body>
</html>
