| <!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"/> |
| <meta http-equiv="X-UA-Compatible" content="IE=9"/> |
| <meta name="generator" content="Doxygen 1.8.4"/> |
| <title>MADlib: Sparse Linear Systems</title> |
| <link href="tabs.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="jquery.js"></script> |
| <script type="text/javascript" src="dynsections.js"></script> |
| <link href="navtree.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="resize.js"></script> |
| <script type="text/javascript" src="navtree.js"></script> |
| <script type="text/javascript"> |
| $(document).ready(initResizable); |
| $(window).load(resizeHeight); |
| </script> |
| <link href="search/search.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="search/search.js"></script> |
| <script type="text/javascript"> |
| $(document).ready(function() { searchBox.OnSelectItem(0); }); |
| </script> |
| <script type="text/x-mathjax-config"> |
| MathJax.Hub.Config({ |
| extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"], |
| jax: ["input/TeX","output/HTML-CSS"], |
| }); |
| </script><script src="../mathjax/MathJax.js"></script> |
| <link href="doxygen.css" rel="stylesheet" type="text/css" /> |
| </head> |
| <body> |
| <div id="top"><!-- do not remove this div, it is closed by doxygen! --> |
| <div id="titlearea"> |
| <table cellspacing="0" cellpadding="0"> |
| <tbody> |
| <tr style="height: 56px;"> |
| <td style="padding-left: 0.5em;"> |
| <div id="projectname">MADlib |
|  <span id="projectnumber">1.1</span> <span style="font-size:10pt; font-style:italic"><a href="../latest/./group__grp__sparse__linear__solver.html"> A newer version is available</a></span> |
| </div> |
| <div id="projectbrief">User Documentation</div> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| </div> |
| <!-- end header part --> |
| <!-- Generated by Doxygen 1.8.4 --> |
| <script type="text/javascript"> |
| var searchBox = new SearchBox("searchBox", "search",false,'Search'); |
| </script> |
| <div id="navrow1" class="tabs"> |
| <ul class="tablist"> |
| <li><a href="index.html"><span>Main Page</span></a></li> |
| <li><a href="modules.html"><span>Modules</span></a></li> |
| <li><a href="files.html"><span>Files</span></a></li> |
| <li> |
| <div id="MSearchBox" class="MSearchBoxInactive"> |
| <span class="left"> |
| <img id="MSearchSelect" src="search/mag_sel.png" |
| onmouseover="return searchBox.OnSearchSelectShow()" |
| onmouseout="return searchBox.OnSearchSelectHide()" |
| alt=""/> |
| <input type="text" id="MSearchField" value="Search" accesskey="S" |
| onfocus="searchBox.OnSearchFieldFocus(true)" |
| onblur="searchBox.OnSearchFieldFocus(false)" |
| onkeyup="searchBox.OnSearchFieldChange(event)"/> |
| </span><span class="right"> |
| <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a> |
| </span> |
| </div> |
| </li> |
| </ul> |
| </div> |
| </div><!-- top --> |
| <div id="side-nav" class="ui-resizable side-nav-resizable"> |
| <div id="nav-tree"> |
| <div id="nav-tree-contents"> |
| <div id="nav-sync" class="sync"></div> |
| </div> |
| </div> |
| <div id="splitbar" style="-moz-user-select:none;" |
| class="ui-resizable-handle"> |
| </div> |
| </div> |
| <script type="text/javascript"> |
| $(document).ready(function(){initNavTree('group__grp__sparse__linear__solver.html','');}); |
| </script> |
| <div id="doc-content"> |
| <!-- window showing the filter options --> |
| <div id="MSearchSelectWindow" |
| onmouseover="return searchBox.OnSearchSelectShow()" |
| onmouseout="return searchBox.OnSearchSelectHide()" |
| onkeydown="return searchBox.OnSearchSelectKey(event)"> |
| <a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark"> </span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark"> </span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark"> </span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark"> </span>Groups</a></div> |
| |
| <!-- iframe showing the search results (closed by default) --> |
| <div id="MSearchResultsWindow"> |
| <iframe src="javascript:void(0)" frameborder="0" |
| name="MSearchResults" id="MSearchResults"> |
| </iframe> |
| </div> |
| |
| <div class="header"> |
| <div class="headertitle"> |
| <div class="title">Sparse Linear Systems<div class="ingroups"><a class="el" href="group__grp__linear__solver.html">Linear Systems</a></div></div> </div> |
| </div><!--header--> |
| <div class="contents"> |
| <div id="dynsection-0" onclick="return toggleVisibility(this)" class="dynheader closed" style="cursor:pointer;"> |
| <img id="dynsection-0-trigger" src="closed.png" alt="+"/> Collaboration diagram for Sparse Linear Systems:</div> |
| <div id="dynsection-0-summary" class="dynsummary" style="display:block;"> |
| </div> |
| <div id="dynsection-0-content" class="dyncontent" style="display:none;"> |
| <center><table><tr><td><div class="center"><iframe scrolling="no" frameborder="0" src="group__grp__sparse__linear__solver.svg" width="347" height="40"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe> |
| </div> |
| </td></tr></table></center> |
| </div> |
| <div class="toc"><b>Contents</b> </p> |
| <ul> |
| <li class="level1"> |
| <a href="#sls_about">About</a> </li> |
| <li class="level1"> |
| <a href="#sls_online_help">Online Help</a> </li> |
| <li class="level1"> |
| <a href="#sls_function">Function Syntax</a> </li> |
| <li class="level1"> |
| <a href="#sls_args">Arguments</a> </li> |
| <li class="level1"> |
| <a href="#sls_opt_params">Optimizer Parameters</a> </li> |
| <li class="level1"> |
| <a href="#sls_output">Output Tables</a> </li> |
| <li class="level1"> |
| <a href="#sls_examples">Examples</a> </li> |
| </ul> |
| </div><p><a class="anchor" id="sls_about"></a></p> |
| <dl class="section user"><dt>About:</dt><dd></dd></dl> |
| <p>The sparse linear systems module implements solution methods for systems of a consistent linear equations. Systems of linear equations take the form: </p> |
| <p class="formulaDsp"> |
| \[ Ax = b \] |
| </p> |
| <p>where \(x \in \mathbb{R}^{n}\), \(A \in \mathbb{R}^{m \times n} \) and \(b \in \mathbb{R}^{m}\). This module accepts sparse matrix input formats for \(A\) and \(b\). We assume that there are no rows of \(A\) where all elements are zero.</p> |
| <dl class="section note"><dt>Note</dt><dd>Algorithms with fail if there is an row of the input matrix containing all zeros.</dd></dl> |
| <p>The algorithms implemented in this module can handle large sparse square linear systems. Currently, the algorithms implemented in this module solve the linear system using direct or iterative methods.</p> |
| <p><a class="anchor" id="sls_online_help"></a></p> |
| <dl class="section user"><dt>Online Help</dt><dd></dd></dl> |
| <p>View short help messages using the following statements: </p> |
| <pre class="fragment">-- Summary of sparse linear systems |
| SELECT madlib.linear_solver_sparse(); |
| |
| -- Function syntax and output table format |
| SELECT madlib.linear_solver_sparse('usage'); |
| |
| -- Syntax for direct methods |
| SELECT madlib.linear_solver_sparse('direct'); |
| |
| -- Syntax for iterative methods |
| SELECT madlib.linear_solver_sparse('iterative'); |
| </pre><p><a class="anchor" id="sls_function"></a></p> |
| <dl class="section user"><dt>Syntax</dt><dd></dd></dl> |
| <pre> |
| linear_solver_sparse(tbl_source_lhs, tbl_source_rhs, tbl_result, |
| row_id, LHS, RHS, grouping_cols := NULL, |
| optimizer := 'direct', |
| optimizer_params := 'algorithm = llt'); |
| </pre><p><a class="anchor" id="sls_args"></a></p> |
| <dl class="section user"><dt>Arguments</dt><dd></dd></dl> |
| <dl class="arglist"> |
| <dt>LHS </dt> |
| <dd><p class="startdd">Text value. The name of the table containing the left hand side matrix. For the LHS matrix, the input data is expected to be of the following form: </p> |
| <pre>{TABLE|VIEW} <em>sourceName</em> ( |
| ... |
| <em>row_id</em> FLOAT8, |
| <em>col_id</em> FLOAT8, |
| <em>value</em> FLOAT8, |
| ... |
| )</pre><p>Here, each row represents a single equation using. The <em> rhs </em> refers to the right hand side of the equations while the <em> lhs</em> refers to the multipliers on the variables on the left hand side of the same equations. </p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>RHS </dt> |
| <dd><p class="startdd">Text value. The name of the table containing the right hand side vector. For the RHS matrix, the input data is expected to be of the following form: </p> |
| <pre>{TABLE|VIEW} <em>sourceName</em> ( |
| ... |
| <em>row_id</em> FLOAT8, |
| <em>value</em> FLOAT8 |
| ... |
| )</pre><p> Here, each row represents a single equation using. The <em> rhs </em> refers to the right hand side of the equations while the <em> lhs</em> refers to the multipliers on the variables on the left hand side of the same equations.</p> |
| <p>Output is stored in the <em>tbl_result</em> </p> |
| <pre class="fragment"> tbl_result | Data Types |
| --------------------|--------------------- |
| solution | DOUBLE PRECISION[] |
| residual_norm | DOUBLE PRECISIOn |
| iters | INTEGER |
| </pre><dl class="section user"><dt>Syntax</dt><dd></dd></dl> |
| <pre> |
| SELECT sparse_linear_sytems('tbl_source_lhs', 'tbl_source_rhs', 'tbl_result', |
| 'row_id', 'LHS', 'RHS', NULL, 'direct', 'algorithm = householderqr'); |
| </pre><dl> |
| <dt>tbl_source_lhs </dt> |
| <dd><p class="startdd">Text value. The name of the table containing the LHS matrix.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>tbl_source_rhs </dt> |
| <dd><p class="startdd">Text value. The name of the table containing the RHS vector.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>tbl_result </dt> |
| <dd><p class="startdd">Text value. The name of the table where the output is saved.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>lhs_row_id </dt> |
| <dd><p class="startdd">Text value. The name of the column storing the 'row id' of the equations.</p> |
| <dl class="section note"><dt>Note</dt><dd>For a system with N equations, the row_id's must be a continuous range of integers from \( 0 \ldots n-1 \).</dd></dl> |
| </dd> |
| <dt>lhs_col_id </dt> |
| <dd><p class="startdd">Text value. The name of the column (in tbl_source_lhs) storing the 'col id' of the equations.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>lhs_value </dt> |
| <dd><p class="startdd">Text value. The name of the column (in tbl_source_lhs) storing the 'value' of the equations.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>rhs_row_id </dt> |
| <dd><p class="startdd">Text value. The name of the column (in tbl_source_rhs) storing the 'col id' of the equations.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>rhs_value </dt> |
| <dd><p class="startdd">Text value. The name of the column (in tbl_source_rhs) storing the 'value' of the equations.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>num_vars </dt> |
| <dd><p class="startdd">Integer value. The number of variables in the linear system. equations.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>grouping_col (optional) </dt> |
| <dd>Text value. Group by columns. Default: NULL. <dl class="section note"><dt>Note</dt><dd>The grouping columns is a placeholder in MADlib V1.1</dd></dl> |
| </dd> |
| <dt>optimizer (optional) </dt> |
| <dd><p class="startdd">Text value. Type of optimizer. Default: 'direct'.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>optimizer_params (optional) </dt> |
| <dd>Text value. Optimizer specific parameters. Default: NULL. </dd> |
| </dl> |
| <p><a class="anchor" id="sls_opt_params"></a></p> |
| <dl class="section user"><dt>Optimizer Parameters</dt><dd></dd></dl> |
| <p>For each optimizer, there are specific parameters that can be tuned for better performance.</p> |
| <dl class="arglist"> |
| <dt>algorithm (default: ldlt) </dt> |
| <dd><p class="startdd"></p> |
| <p>There are several algorithms that can be classified as 'direct' methods of solving linear systems. Madlib functions provide various algorithmic options available for users.</p> |
| <p>The following table provides a guideline on the choice of algorithm based on conditions on the A matrix, speed of the algorithms and numerical stability. </p> |
| <pre class="fragment">Algorithm | Contitions on A | Speed | Memory |
| ---------------------------------------------------------- |
| llt | Sym. Pos Def | ++ | --- |
| ldlt | Sym. Pos Def | ++ | --- |
| </pre><p>For speed '++' is faster than '+', which is faster than '-'. For accuracy '+++' is better than '++'. For memory, '-' uses less memory than '–'.</p> |
| <p>Note: ldlt is often preferred over llt</p> |
| <p>There are several algorithms that can be classified as 'iterative' methods of solving linear systems. Madlib functions provide various algorithmic options available for users.</p> |
| <p>The following table provides a guideline on the choice of algorithm based on conditions on the A matrix, speed of the algorithms and numerical stability.</p> |
| <pre class="fragment"> Algorithm | Contitions on A | Speed | Memory | Convergence |
| ---------------------------------------------------------------------- |
| cg-mem | Sym. Pos Def | +++ | - | ++ |
| bicgstab-mem | Square | ++ | - | + |
| precond-cg-mem | Sym. Pos Def | ++ | - | +++ |
| precond-bicgstab-mem | Square | + | - | ++ |
| |
| For memory, '-' uses less memory than '--'. |
| For speed, '++' is faster than '+'. |
| </pre><p>Details:</p> |
| <ol type="1"> |
| <li><b>cg-mem: </b> In memory conjugate gradient with diagonal preconditioners.</li> |
| <li><b>bicgstab-mem: </b> Bi-conjugate gradient (equivalent to performing CG on the least squares formulation of Ax=b) with incomplete LU preconditioners.</li> |
| <li><b>precond-cg-mem:</b> In memory conjugate gradient with diagonal preconditioners.</li> |
| <li><b>bicgstab-mem: </b> Bi-conjugate gradient (equivalent to performing CG on the least squares formulation of Ax=b) with incomplete LU preconditioners. </li> |
| </ol> |
| <p class="enddd"></p> |
| </dd> |
| <dt>toler (default: 1e-5) </dt> |
| <dd><p class="startdd">Termination tolerance (applicable only for iterative methods) which determines the stopping criterion (with respect to residual norm) for iterative methods. </p> |
| <p class="enddd"></p> |
| </dd> |
| </dl> |
| <p><a class="anchor" id="sls_output"></a></p> |
| <dl class="section user"><dt>Output statistics</dt><dd></dd></dl> |
| <dl class="arglist"> |
| <dt>solution </dt> |
| <dd><p class="startdd">The solution is an array (of double precision) with the variables in the same order as that provided as input in the 'left_hand_side' column name of the 'source_table' </p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>residual_norm </dt> |
| <dd><p class="startdd">Computes the scaled residual norm, defined as \( \frac{|Ax - b|}{|b|} \) gives the user an indication of the accuracy of the solution. </p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>iters </dt> |
| <dd><p class="startdd">The number of iterations required by the algorithm (only applicable for iterative algorithms) . The output is NULL for direct' methods. </p> |
| <p class="enddd"></p> |
| </dd> |
| </dl> |
| <p class="enddd"><a class="anchor" id="sls_examples"></a></p> |
| <dl class="section user"><dt>Examples:</dt><dd><ol type="1"> |
| <li>Create the sample data set: <pre class="fragment">sql> DROP TABLE IF EXISTS sparse_linear_systems_lhs; |
| CREATE TABLE sparse_linear_systems_lhs ( |
| rid INTEGER NOT NULL, |
| cid INTEGER, |
| val DOUBLE PRECISION |
| ); |
| |
| DROP TABLE IF EXISTS sparse_linear_systems_rhs; |
| CREATE TABLE sparse_linear_systems_rhs ( |
| rid INTEGER NOT NULL, |
| val DOUBLE PRECISION |
| ); |
| |
| |
| INSERT INTO sparse_linear_systems_lhs(rid, cid, val) VALUES |
| (0, 0, 1), |
| (1, 1, 1), |
| (2, 2, 1), |
| (3, 3, 1); |
| |
| INSERT INTO sparse_linear_systems_rhs(rid, val) VALUES |
| (0, 10), |
| (1, 20), |
| (2, 30); |
| </pre></li> |
| <li>Solve the linear systems with default parameters <pre class="fragment">sql> SELECT madlib.linear_solver_sparse( |
| 'sparse_linear_systems_lhs', |
| 'sparse_linear_systems_rhs', |
| 'output_table', |
| 'rid', |
| 'cid', |
| 'val', |
| 'rid', |
| 'val', |
| 4); |
| </pre></li> |
| <li>Obtain the output from the output table <pre class="fragment">sql> SELECT * FROM output_table; |
| --------------------+------------------------------------- |
| solution | {10,20,30,0} |
| residual_norm | 0 |
| iters | NULL |
| </pre></li> |
| <li>Chose a different algorithm than the default algorithm <pre class="fragment">drop table if exists result_table; |
| |
| SELECT madlib.linear_solver_sparse( |
| 'sparse_linear_systems_lhs', |
| 'sparse_linear_systems_rhs', |
| 'output_table', |
| 'rid', |
| 'cid', |
| 'val', |
| 'rid', |
| 'val', |
| 4, |
| NULL, |
| 'direct', |
| 'algorithm=llt'); |
| |
| -# Chose a different algorithm than the default algorithm |
| \verbatim |
| drop table if exists result_table; |
| madlib.linear_solver_sparse( |
| 'sparse_linear_systems_lhs', |
| 'sparse_linear_systems_rhs', |
| 'output_table', |
| 'rid', |
| 'cid', |
| 'val', |
| 'rid', |
| 'val', |
| 4, |
| NULL, |
| 'iterative', |
| 'algorithm=cg-mem, toler=1e-5'); |
| </pre></li> |
| </ol> |
| </dd></dl> |
| <dl class="section see"><dt>See Also</dt><dd>File sparse_linear_sytems.sql_in documenting the SQL functions. </dd></dl> |
| </dd> |
| </dl> |
| </div><!-- contents --> |
| </div><!-- doc-content --> |
| <!-- start footer part --> |
| <div id="nav-path" class="navpath"><!-- id is needed for treeview function! --> |
| <ul> |
| <li class="footer">Generated on Wed Aug 21 2013 16:09:52 for MADlib by |
| <a href="http://www.doxygen.org/index.html"> |
| <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.4 </li> |
| </ul> |
| </div> |
| </body> |
| </html> |
