http://ejml.org/wiki/index.php?title=Solving_Linear_Systems&feed=atom&action=history
Solving Linear Systems - Revision history
2024-03-29T14:24:31Z
Revision history for this page on the wiki
MediaWiki 1.35.11
http://ejml.org/wiki/index.php?title=Solving_Linear_Systems&diff=221&oldid=prev
Peter at 14:15, 18 May 2017
2017-05-18T14:15:33Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 14:15, 18 May 2017</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l29" >Line 29:</td>
<td colspan="2" class="diff-lineno">Line 29:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>if( !<del class="diffchange diffchange-inline">CommonOps</del>.solve(A,b,x) ) {</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>if( !<ins class="diffchange diffchange-inline">CommonOps_DDRM</ins>.solve(A,b,x) ) {</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> throw new IllegalArgument("Singular matrix");</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> throw new IllegalArgument("Singular matrix");</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>}</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l56" >Line 56:</td>
<td colspan="2" class="diff-lineno">Line 56:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Low level Linear Solvers =</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Low level Linear Solvers =</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Low level linear solvers in EJML all implement the <del class="diffchange diffchange-inline">[http://ejml.org/javadoc/</del>org/ejml/interfaces/linsol/LinearSolver.html LinearSolver<del class="diffchange diffchange-inline">] </del>interface. It provides a lot more power than the high level interfaces but is also more difficult to use and require more diligence. For example, you can no longer assume that it won't modify the input matrices!</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Low level linear solvers in EJML all implement the <ins class="diffchange diffchange-inline">{{DocLink|</ins>org/ejml/interfaces/linsol/LinearSolver.html<ins class="diffchange diffchange-inline">|</ins>LinearSolver<ins class="diffchange diffchange-inline">}} </ins>interface. It provides a lot more power than the high level interfaces but is also more difficult to use and require more diligence. For example, you can no longer assume that it won't modify the input matrices!</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== LinearSolver == </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== LinearSolver == </div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l63" >Line 63:</td>
<td colspan="2" class="diff-lineno">Line 63:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>public interface LinearSolver< T extends <del class="diffchange diffchange-inline">Matrix64F</del>> {</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>public interface LinearSolver< T extends <ins class="diffchange diffchange-inline">Matrix</ins>> {</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> public boolean setA( T A );</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> public boolean setA( T A );</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l83" >Line 83:</td>
<td colspan="2" class="diff-lineno">Line 83:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></syntaxhighlight></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></syntaxhighlight></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Each linear solver implementation is built around a different decomposition. The best way to create a new LinearSolver instance is with <del class="diffchange diffchange-inline">[http:</del>//ejml<del class="diffchange diffchange-inline">.org/javadoc</del>/<del class="diffchange diffchange-inline">org</del>/<del class="diffchange diffchange-inline">ejml</del>/factory/<del class="diffchange diffchange-inline">LinearSolverFactory</del>.html <del class="diffchange diffchange-inline">LinearSolverFactory]</del>. It provides an easy way to select the correct solver without plowing through the documentation.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Each linear solver implementation is built around a different decomposition. The best way to create a new LinearSolver instance is with <ins class="diffchange diffchange-inline">{{DocLink|javadoc</ins>/<ins class="diffchange diffchange-inline">org</ins>/ejml/<ins class="diffchange diffchange-inline">dense</ins>/<ins class="diffchange diffchange-inline">row</ins>/factory/<ins class="diffchange diffchange-inline">LinearSolverFactory_DDRM</ins>.html<ins class="diffchange diffchange-inline">|LinearSolverFactory_DDRM}}</ins>. It provides an easy way to select the correct solver without plowing through the documentation.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Two steps are required to solve a system with a LinearSolver, as is shown below:</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Two steps are required to solve a system with a LinearSolver, as is shown below:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>LinearSolver<<del class="diffchange diffchange-inline">DenseMatrix64F</del>> solver = <del class="diffchange diffchange-inline">LinearSolverFactory</del>.qr(A.numRows,A.numCols);</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>LinearSolver<<ins class="diffchange diffchange-inline">DMatrixRMaj</ins>> solver = <ins class="diffchange diffchange-inline">LinearSolverFactory_DDRM</ins>.qr(A.numRows,A.numCols);</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>if( !solver.setA(A) ) {</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>if( !solver.setA(A) ) {</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> throw new IllegalArgument("Singular matrix");</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> throw new IllegalArgument("Singular matrix");</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l117" >Line 117:</td>
<td colspan="2" class="diff-lineno">Line 117:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>LinearSolver<<del class="diffchange diffchange-inline">DenseMatrix64F</del>> solver = <del class="diffchange diffchange-inline">LinearSolverFactory</del>.leastSquares();</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>LinearSolver<<ins class="diffchange diffchange-inline">DMatrixRMaj</ins>> solver = <ins class="diffchange diffchange-inline">LinearSolverFactory_DDRM</ins>.leastSquares();</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>solver = new LinearSolverSafe<<del class="diffchange diffchange-inline">DenseMatrix64F</del>>(solver);</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>solver = new LinearSolverSafe<<ins class="diffchange diffchange-inline">DMatrixRMaj</ins>>(solver);</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></syntaxhighlight></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></syntaxhighlight></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l126" >Line 126:</td>
<td colspan="2" class="diff-lineno">Line 126:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>LinearSolver<<del class="diffchange diffchange-inline">DenseMatrix64F</del>> pinv = <del class="diffchange diffchange-inline">LinearSolverFactory</del>.pseudoInverse(true);</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>LinearSolver<<ins class="diffchange diffchange-inline">DMatrixRMaj</ins>> pinv = <ins class="diffchange diffchange-inline">LinearSolverFactory_DDRM</ins>.pseudoInverse(true);</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></syntaxhighlight></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></syntaxhighlight></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l134" >Line 134:</td>
<td colspan="2" class="diff-lineno">Line 134:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== AdjustableLinearSolver ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== AdjustableLinearSolver ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In situations where rows from the linear system are added or removed (see [[Example Polynomial Fitting]]) an <del class="diffchange diffchange-inline">AdjustableLinearSolver </del>can be used to efficiently resolve the modified system. <del class="diffchange diffchange-inline">AdjustableLinearSolver </del>is an extension of LinearSolver that adds addRowToA() and removeRowFromA(). These functions add and remove rows from A respectively. After being involved the solution can be recomputed by calling solve() again.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In situations where rows from the linear system are added or removed (see [[Example Polynomial Fitting]]) an <ins class="diffchange diffchange-inline">AdjustableLinearSolver_DDRM </ins>can be used to efficiently resolve the modified system. <ins class="diffchange diffchange-inline">AdjustableLinearSolver_DDRM </ins>is an extension of LinearSolver that adds addRowToA() and removeRowFromA(). These functions add and remove rows from A respectively. After being involved the solution can be recomputed by calling solve() again.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="java"></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">AdjustableLinearSolver </del>solver = <del class="diffchange diffchange-inline">LinearSolverFactory</del>.adjustable();</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">AdjustableLinearSolver_DDRM </ins>solver = <ins class="diffchange diffchange-inline">LinearSolverFactory_DDRM</ins>.adjustable();</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>if( !solver.setA(A) ) {</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>if( !solver.setA(A) ) {</div></td></tr>
</table>
Peter
http://ejml.org/wiki/index.php?title=Solving_Linear_Systems&diff=58&oldid=prev
Peter: Created page with "A fundamental problem in linear algebra is solving systems of linear equations. A linear system is any equation than can be expressed in this format: <pre> A*x = b </pre> w..."
2015-03-22T16:02:23Z
<p>Created page with "A fundamental problem in linear algebra is solving systems of linear equations. A linear system is any equation than can be expressed in this format: <pre> A*x = b </pre> w..."</p>
<p><b>New page</b></p><div>A fundamental problem in linear algebra is solving systems of linear equations. A linear system is any equation than can be expressed in this format:<br />
<br />
<pre><br />
A*x = b<br />
</pre><br />
<br />
where ''A'' is m by n, ''x'' is n by o, and ''b'' is m by o. Most of the time o=1. The best way to solve these equations depends on the structure of the matrix ''A''. For example, if it's square and positive definite then [http://ejml.org/javadoc/org/ejml/interfaces/decomposition/CholeskyDecomposition.html Cholesky] decomposition is the way to go. On the other hand if it is tall m > n, then [http://ejml.org/javadoc/org/ejml/interfaces/decomposition/QRDecomposition.html QR] is the way to go. <br />
<br />
Each of the three interfaces (Procedural, SimpleMatrix, Equations) provides high level ways to solve linear systems which don't require you to specify the underlying algorithm. While convenient, these are not always the best approach in high performance situations. They create/destroy memory and don't provide you with access to their full functionality. If the best performance is needed then you should use a LinearSolver or one of its derived interfaces for a specific family of algorithms.<br />
<br />
First a description is provided on how to solve linear systems using Procedural, SimpleMatrix, and then Equations. After that an overview of LinearSolver is presented.<br />
<br />
= High Level Interfaces =<br />
<br />
All high level interfaces essentially use the same code at the low level, which is the Procedural interface. This means that they have the same strengths and weaknesses. Their strength is simplicity. They will automatically select LU and QR decomposition, depending on the matrix's shape. <br />
<br />
You should use the lower level LinearSolver if any of the following are true:<br />
* Your matrix can some times be singular<br />
* You wish to perform a pseudo inverse<br />
* You need to avoid creating new memory<br />
* You need to select a specific decomposition<br />
* You need access to the low level decomposition<br />
<br />
The case of singular or nearly singular matrices is worth discussing more. All of these high level approaches do attempt to detect singular matrices. The problem is that they aren't reliable and no tweaking of thresholds will make them reliable. If you are in a situation where you need to come up with a solution and it might be singular then you really need to know what you are doing. If a system is singular it means there are an infinite number of solutions. <br />
<br />
== Procedural ==<br />
<br />
The way to solve linear systems in the Procedural interface is with CommonOps.solve(). Make sure you check it's return value to see if it failed! It ''might'' fail if the matrix is singular or nearly singular.<br />
<br />
<syntaxhighlight lang="java"><br />
if( !CommonOps.solve(A,b,x) ) {<br />
throw new IllegalArgument("Singular matrix");<br />
}<br />
</syntaxhighlight><br />
<br />
== SimpleMatrix ==<br />
<br />
<syntaxhighlight lang="java"><br />
try {<br />
SimpleMatrix x = A.solve(b);<br />
} catch ( SingularMatrixException e ) {<br />
throw new IllegalArgument("Singular matrix");<br />
}<br />
</syntaxhighlight><br />
<br />
SingularMatrixException is a RuntimeException and you technically don't have to catch it. If you don't catch it, it will take down your whole application if the matrix is singular!<br />
<br />
== Equations ==<br />
<br />
<syntaxhighlight lang="java"><br />
eq.process("x=b/A");<br />
</syntaxhighlight><br />
<br />
If it's singular it will throw a RuntimeException.<br />
<br />
= Low level Linear Solvers =<br />
<br />
Low level linear solvers in EJML all implement the [http://ejml.org/javadoc/org/ejml/interfaces/linsol/LinearSolver.html LinearSolver] interface. It provides a lot more power than the high level interfaces but is also more difficult to use and require more diligence. For example, you can no longer assume that it won't modify the input matrices!<br />
<br />
== LinearSolver == <br />
<br />
The LinearSolver interface is designed to be easy to use and to provide most of the power that comes from directly using a decomposition would provide.<br />
<br />
<syntaxhighlight lang="java"><br />
public interface LinearSolver< T extends Matrix64F> {<br />
<br />
public boolean setA( T A );<br />
<br />
public T getA();<br />
<br />
public double quality();<br />
<br />
public void solve( T B , T X );<br />
<br />
public void invert( T A_inv );<br />
<br />
public boolean modifiesA();<br />
<br />
public boolean modifiesB();<br />
<br />
public <D extends DecompositionInterface>D getDecomposition();<br />
}<br />
</syntaxhighlight><br />
<br />
Each linear solver implementation is built around a different decomposition. The best way to create a new LinearSolver instance is with [http://ejml.org/javadoc/org/ejml/factory/LinearSolverFactory.html LinearSolverFactory]. It provides an easy way to select the correct solver without plowing through the documentation.<br />
<br />
<br />
Two steps are required to solve a system with a LinearSolver, as is shown below:<br />
<syntaxhighlight lang="java"><br />
LinearSolver<DenseMatrix64F> solver = LinearSolverFactory.qr(A.numRows,A.numCols);<br />
if( !solver.setA(A) ) {<br />
throw new IllegalArgument("Singular matrix");<br />
}<br />
<br />
if( solver.quality() <= 1e-8 )<br />
throw new IllegalArgument("Nearly singular matrix");<br />
<br />
solver.solve(b,x);<br />
</syntaxhighlight><br />
<br />
As with the high-level interfaces you can't trust algorithms such as QR, LU, or Cholesky to detect singular matrices! Sometimes they will work and sometimes they will not. Even adjusting the quality threshold won't fix the problem in all situations.<br />
<br />
Additional capabilities included in LinearSolver are:<br />
<br />
* invert()<br />
** Will invert a matrix more efficiently than solve() can.<br />
* quality()<br />
** Returns a positive number which if it is small indicates a singular or nearly singular system system. Much faster to compute than the SVD.<br />
* modifiesA() and modifiesB()<br />
** To reduce memory requirements, most LinearSolvers will modify the 'A' and store the decomposition inside of it. Some do the same for 'B' These function tell the user if the inputs are being modified or not.<br />
* getDecomposition()<br />
** Provides access to the internal decomposition used.<br />
<br />
<br />
== LinearSolverSafe ==<br />
If the input matrices 'A' and 'B' should not be modified then LinearSolverSafe is a convenient way to ensure that precondition:<br />
<br />
<syntaxhighlight lang="java"><br />
LinearSolver<DenseMatrix64F> solver = LinearSolverFactory.leastSquares();<br />
solver = new LinearSolverSafe<DenseMatrix64F>(solver);<br />
</syntaxhighlight><br />
<br />
== Pseudo Inverse ==<br />
<br />
EJML provides two different pseudo inverses. One is SVD based and the other QRP. QRP stands for QR with column pivots. QRP can be thought of as a light weight SVD, much faster to compute but doesn't handle singular matrices quite as well.<br />
<br />
<syntaxhighlight lang="java"><br />
LinearSolver<DenseMatrix64F> pinv = LinearSolverFactory.pseudoInverse(true);<br />
</syntaxhighlight><br />
<br />
This will create an SVD based pseudo inverse. Otherwise if you specify false then it will create a QRP pseudo-inverse.<br />
<br />
<br />
== AdjustableLinearSolver ==<br />
<br />
In situations where rows from the linear system are added or removed (see [[Example Polynomial Fitting]]) an AdjustableLinearSolver can be used to efficiently resolve the modified system. AdjustableLinearSolver is an extension of LinearSolver that adds addRowToA() and removeRowFromA(). These functions add and remove rows from A respectively. After being involved the solution can be recomputed by calling solve() again.<br />
<br />
<syntaxhighlight lang="java"><br />
AdjustableLinearSolver solver = LinearSolverFactory.adjustable();<br />
<br />
if( !solver.setA(A) ) {<br />
throw new IllegalArgument("Singular matrix");<br />
}<br />
<br />
solver.solve(b,x);<br />
<br />
// add a row<br />
double row[] = new double[N];<br />
<br />
... code ...<br />
<br />
solver.addRowToA(row,2);<br />
<br />
.... adjust b and x ....<br />
<br />
solver.solve(b,x); <br />
<br />
// remove a row<br />
solver.removeRowFromA(7);<br />
<br />
.... adjust b and x ....<br />
<br />
solver.solve(b,x);<br />
</syntaxhighlight></div>
Peter