<!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: Eliminator< Field, Matrix > Class Template Reference</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><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 class="current"><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="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li><a href="hierarchy.html"><span>Class Hierarchy</span></a></li>
<li><a href="functions.html"><span>Data Fields</span></a></li>
</ul>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="namespace_lin_box.html">LinBox</a> </li>
<li class="navelem"><a class="el" href="class_lin_box_1_1_eliminator.html">Eliminator</a> </li>
</ul>
</div>
</div>
<div class="header">
<div class="summary">
<a href="#pub-types">Public Types</a> |
<a href="#pub-methods">Public Member Functions</a> </div>
<div class="headertitle">
<div class="title">Eliminator< Field, Matrix > Class Template Reference</div> </div>
</div>
<div class="contents">
<!-- doxytag: class="LinBox::Eliminator" -->
<p>Elimination system.
<a href="class_lin_box_1_1_eliminator.html#details">More...</a></p>
<p><code>#include <eliminator.h></code></p>
<table class="memberdecls">
<tr><td colspan="2"><h2><a name="pub-types"></a>
Public Types</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">typedef std::pair< unsigned <br class="typebreak"/>
int, unsigned int > </td><td class="memItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#a2949010c04572ecfe6d33a7c9a57cfed">Transposition</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight"><a class="el" href="class_lin_box_1_1_permutation.html" title="size is n.">Permutation</a>. <a href="#a2949010c04572ecfe6d33a7c9a57cfed"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#a68d1290f1fef88383353e7f6fb7fbddb">Eliminator</a> (const Field &F, unsigned int N)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Constructor. <a href="#a68d1290f1fef88383353e7f6fb7fbddb"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a6fa93ac93ff3353a12868bd719df65b6"></a><!-- doxytag: member="LinBox::Eliminator::~Eliminator" ref="a6fa93ac93ff3353a12868bd719df65b6" args="()" -->
 </td><td class="memItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#a6fa93ac93ff3353a12868bd719df65b6">~Eliminator</a> ()</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Destructor. <br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template<class Matrix1 , class Matrix2 , class Matrix3 , class Matrix4 > </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">void </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#a2579428566172f987a51f7df185d20ea">twoSidedGaussJordan</a> (Matrix1 &Ainv, Permutation &P, Matrix2 &Tu, Permutation &Q, Matrix3 &Tv, const Matrix4 &A, unsigned int &rank)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Two-sided Gauss-Jordan transform. <a href="#a2579428566172f987a51f7df185d20ea"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">Matrix & </td><td class="memItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#a14840f4f5f70dc9ee50d72d2b0151169">permuteAndInvert</a> (Matrix &W, std::vector< bool > &S, std::vector< bool > &T, std::list< unsigned int > &rightPriorityIdx, Permutation &Qp, unsigned int &rank, const Matrix &A)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Permute the input and invert it. <a href="#a14840f4f5f70dc9ee50d72d2b0151169"></a><br/></td></tr>
<tr><td class="memTemplParams" colspan="2">template<class Matrix1 , class Matrix2 , class Matrix3 , class Matrix4 > </td></tr>
<tr><td class="memTemplItemLeft" align="right" valign="top">Matrix1 & </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#a78fda6ca7ca57f9f4f4df16cea810e21">gaussJordan</a> (Matrix1 &U, std::vector< unsigned int > &profile, Permutation &P, Matrix2 &Tu, Permutation &Q, Matrix3 &Tv, unsigned int &rank, typename Field::Element &det, const Matrix4 &A)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Perform a Gauss-Jordan transform using a recursive algorithm. <a href="#a78fda6ca7ca57f9f4f4df16cea810e21"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a1eb362aa7606d869e075efe060b43daf"></a><!-- doxytag: member="LinBox::Eliminator::getTotalTime" ref="a1eb362aa7606d869e075efe060b43daf" args="() const " -->
double </td><td class="memItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#a1eb362aa7606d869e075efe060b43daf">getTotalTime</a> () const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Retrieve the total user time spent permuting and inverting. <br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="ae300afd99241e31608f71e088e68e40b"></a><!-- doxytag: member="LinBox::Eliminator::getInvertTime" ref="ae300afd99241e31608f71e088e68e40b" args="() const " -->
double </td><td class="memItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#ae300afd99241e31608f71e088e68e40b">getInvertTime</a> () const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Retrieve the total user time spent inverting only. <br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="aaccf2f40fa06aa178c8f0cd58c673605"></a><!-- doxytag: member="LinBox::Eliminator::writeFilter" ref="aaccf2f40fa06aa178c8f0cd58c673605" args="(std::ostream &out, const std::vector< bool > &v) const " -->
std::ostream & </td><td class="memItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#aaccf2f40fa06aa178c8f0cd58c673605">writeFilter</a> (std::ostream &out, const std::vector< bool > &v) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Write the filter vector to the given output stream. <br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="aa59015c40e014d5b2ea1a0b1d2dbb31d"></a><!-- doxytag: member="LinBox::Eliminator::writePermutation" ref="aa59015c40e014d5b2ea1a0b1d2dbb31d" args="(std::ostream &out, const Permutation &P) const " -->
std::ostream & </td><td class="memItemRight" valign="bottom"><a class="el" href="class_lin_box_1_1_eliminator.html#aa59015c40e014d5b2ea1a0b1d2dbb31d">writePermutation</a> (std::ostream &out, const Permutation &P) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Write the given permutation to the output stream. <br/></td></tr>
</table>
<hr/><a name="details" id="details"></a><h2>Detailed Description</h2>
<div class="textblock"><h3>template<class Field, class Matrix = DenseMatrixBase<typename Field::Element>><br/>
class LinBox::Eliminator< Field, Matrix ></h3>
<p>Elimination system. </p>
<p>This is the supporting elimination system for a lookahead-based variant of block Lanczos. </p>
</div><hr/><h2>Member Typedef Documentation</h2>
<a class="anchor" id="a2949010c04572ecfe6d33a7c9a57cfed"></a><!-- doxytag: member="LinBox::Eliminator::Transposition" ref="a2949010c04572ecfe6d33a7c9a57cfed" args="" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">typedef std::pair<unsigned int, unsigned int> <a class="el" href="class_lin_box_1_1_eliminator.html#a2949010c04572ecfe6d33a7c9a57cfed">Transposition</a></td>
</tr>
</table>
</div>
<div class="memdoc">
<p><a class="el" href="class_lin_box_1_1_permutation.html" title="size is n.">Permutation</a>. </p>
<p>A permutation is represented as a vector of pairs, each pair representing a transposition. Thus a permutation requires <code>O(n log n)</code> storage and <code>O(n log n)</code> application time, as opposed to the lower bound of <code>O(n)</code> for both. However, this allows us to decompose a permutation easily into its factors, thus eliminating the need for additional auxillary storage in each level of the Gauss-Jordan transform recursion. Additionally, we expect to use this with dense matrices that are "close to
generic", meaning that the rank should be high and there should be relatively little need for transpositions. In practice, we therefore expect this to beat the vector representation. The use of this representation does not affect the analysis of the Gauss-Jordan transform, since each step where a permutation is applied also requires matrix multiplication, which is strictly more expensive. </p>
</div>
</div>
<hr/><h2>Constructor & Destructor Documentation</h2>
<a class="anchor" id="a68d1290f1fef88383353e7f6fb7fbddb"></a><!-- doxytag: member="LinBox::Eliminator::Eliminator" ref="a68d1290f1fef88383353e7f6fb7fbddb" args="(const Field &F, unsigned int N)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_lin_box_1_1_eliminator.html">Eliminator</a> </td>
<td>(</td>
<td class="paramtype">const Field & </td>
<td class="paramname"><em>F</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int </td>
<td class="paramname"><em>N</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Constructor. </p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramname">F</td><td>Field over which to operate </td></tr>
<tr><td class="paramname">N</td><td></td></tr>
</table>
</dd>
</dl>
</div>
</div>
<hr/><h2>Member Function Documentation</h2>
<a class="anchor" id="a2579428566172f987a51f7df185d20ea"></a><!-- doxytag: member="LinBox::Eliminator::twoSidedGaussJordan" ref="a2579428566172f987a51f7df185d20ea" args="(Matrix1 &Ainv, Permutation &P, Matrix2 &Tu, Permutation &Q, Matrix3 &Tv, const Matrix4 &A, unsigned int &rank)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void twoSidedGaussJordan </td>
<td>(</td>
<td class="paramtype">Matrix1 & </td>
<td class="paramname"><em>Ainv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Permutation & </td>
<td class="paramname"><em>P</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Matrix2 & </td>
<td class="paramname"><em>Tu</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Permutation & </td>
<td class="paramname"><em>Q</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Matrix3 & </td>
<td class="paramname"><em>Tv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const Matrix4 & </td>
<td class="paramname"><em>A</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int & </td>
<td class="paramname"><em>rank</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Two-sided Gauss-Jordan transform. </p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramname">Ainv</td><td><a class="el" href="class_lin_box_1_1_inverse.html" title="A Blackbox for the inverse.">Inverse</a> of nonsingular part of A </td></tr>
<tr><td class="paramname">Tu</td><td>Row dependencies </td></tr>
<tr><td class="paramname">Tv</td><td>Column dependencies </td></tr>
<tr><td class="paramname">P</td><td>Row permutation </td></tr>
<tr><td class="paramname">Q</td><td>Column permutation </td></tr>
<tr><td class="paramname">A</td><td>Input matrix </td></tr>
<tr><td class="paramname">rank</td><td>Rank of A </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="a14840f4f5f70dc9ee50d72d2b0151169"></a><!-- doxytag: member="LinBox::Eliminator::permuteAndInvert" ref="a14840f4f5f70dc9ee50d72d2b0151169" args="(Matrix &W, std::vector< bool > &S, std::vector< bool > &T, std::list< unsigned int > &rightPriorityIdx, Permutation &Qp, unsigned int &rank, const Matrix &A)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">Matrix & permuteAndInvert </td>
<td>(</td>
<td class="paramtype">Matrix & </td>
<td class="paramname"><em>W</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">std::vector< bool > & </td>
<td class="paramname"><em>S</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">std::vector< bool > & </td>
<td class="paramname"><em>T</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">std::list< unsigned int > & </td>
<td class="paramname"><em>rightPriorityIdx</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Permutation & </td>
<td class="paramname"><em>Qp</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int & </td>
<td class="paramname"><em>rank</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const Matrix & </td>
<td class="paramname"><em>A</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Permute the input and invert it. </p>
<p>Compute the pseudoinverse of the input matrix A and return it. First apply the permutation given by the lists leftPriorityIdx and rightPriorityIdx to the input matrix so that independent columns and rows are more likely to be found on the first indices in those lists. Zero out the rows and columns of the inverse corresponding to dependent rows and columns of the input. Set S and T to boolean vectors such that S^T A T is invertible and of maximal size.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramname">W</td><td>Output inverse </td></tr>
<tr><td class="paramname">S</td><td>Output vector S </td></tr>
<tr><td class="paramname">T</td><td>Output vector T </td></tr>
<tr><td class="paramname">rightPriorityIdx</td><td>Priority indices on the right </td></tr>
<tr><td class="paramname">Qp</td><td></td></tr>
<tr><td class="paramname">rank</td><td></td></tr>
<tr><td class="paramname">A</td><td>Input matrix A </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>Reference to inverse matrix </dd></dl>
</div>
</div>
<a class="anchor" id="a78fda6ca7ca57f9f4f4df16cea810e21"></a><!-- doxytag: member="LinBox::Eliminator::gaussJordan" ref="a78fda6ca7ca57f9f4f4df16cea810e21" args="(Matrix1 &U, std::vector< unsigned int > &profile, Permutation &P, Matrix2 &Tu, Permutation &Q, Matrix3 &Tv, unsigned int &rank, typename Field::Element &det, const Matrix4 &A)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">Matrix1 & gaussJordan </td>
<td>(</td>
<td class="paramtype">Matrix1 & </td>
<td class="paramname"><em>U</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">std::vector< unsigned int > & </td>
<td class="paramname"><em>profile</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Permutation & </td>
<td class="paramname"><em>P</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Matrix2 & </td>
<td class="paramname"><em>Tu</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Permutation & </td>
<td class="paramname"><em>Q</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">Matrix3 & </td>
<td class="paramname"><em>Tv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int & </td>
<td class="paramname"><em>rank</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">typename Field::Element & </td>
<td class="paramname"><em>det</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const Matrix4 & </td>
<td class="paramname"><em>A</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Perform a Gauss-Jordan transform using a recursive algorithm. </p>
<p>Upon completion, we have UPA = R, where R is of reduced row echelon form</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table class="params">
<tr><td class="paramname">U</td><td>Output matrix U </td></tr>
<tr><td class="paramname">P</td><td>Output permutation P </td></tr>
<tr><td class="paramname">A</td><td>Input matrix A </td></tr>
<tr><td class="paramname">profile</td><td></td></tr>
<tr><td class="paramname">Tu</td><td></td></tr>
<tr><td class="paramname">Q</td><td></td></tr>
<tr><td class="paramname">Tv</td><td></td></tr>
<tr><td class="paramname">rank</td><td></td></tr>
<tr><td class="paramname">det</td><td></td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>Reference to U </dd></dl>
</div>
</div>
<hr/>The documentation for this class was generated from the following files:<ul>
<li>eliminator.h</li>
<li>eliminator.inl</li>
</ul>
</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>
