| <!-- HTML header for doxygen 1.8.4--> |
| <!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.13"/> |
| <meta name="keywords" content="madlib,postgres,greenplum,machine learning,data mining,deep learning,ensemble methods,data science,market basket analysis,affinity analysis,pca,lda,regression,elastic net,huber white,proportional hazards,k-means,latent dirichlet allocation,bayes,support vector machines,svm"/> |
| <title>MADlib: Dense 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="navtreedata.js"></script> |
| <script type="text/javascript" src="navtree.js"></script> |
| <script type="text/javascript"> |
| $(document).ready(initResizable); |
| </script> |
| <link href="search/search.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="search/searchdata.js"></script> |
| <script type="text/javascript" src="search/search.js"></script> |
| <script type="text/javascript"> |
| $(document).ready(function() { init_search(); }); |
| </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 type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js"></script> |
| <!-- hack in the navigation tree --> |
| <script type="text/javascript" src="eigen_navtree_hacks.js"></script> |
| <link href="doxygen.css" rel="stylesheet" type="text/css" /> |
| <link href="madlib_extra.css" rel="stylesheet" type="text/css"/> |
| <!-- google analytics --> |
| <script> |
| (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ |
| (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), |
| m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) |
| })(window,document,'script','//www.google-analytics.com/analytics.js','ga'); |
| ga('create', 'UA-45382226-1', 'madlib.apache.org'); |
| ga('send', 'pageview'); |
| </script> |
| </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 id="projectlogo"><a href="http://madlib.apache.org"><img alt="Logo" src="madlib.png" height="50" style="padding-left:0.5em;" border="0"/ ></a></td> |
| <td style="padding-left: 0.5em;"> |
| <div id="projectname"> |
| <span id="projectnumber">1.19.0</span> |
| </div> |
| <div id="projectbrief">User Documentation for Apache MADlib</div> |
| </td> |
| <td> <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> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| </div> |
| <!-- end header part --> |
| <!-- Generated by Doxygen 1.8.13 --> |
| <script type="text/javascript"> |
| var searchBox = new SearchBox("searchBox", "search",false,'Search'); |
| </script> |
| </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__dense__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)"> |
| </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">Dense Linear Systems<div class="ingroups"><a class="el" href="group__grp__other__functions.html">Utilities</a> » <a class="el" href="group__grp__linear__solver.html">Linear Solvers</a></div></div> </div> |
| </div><!--header--> |
| <div class="contents"> |
| <div class="toc"><b>Contents</b> <ul> |
| <li class="level1"> |
| <a href="#dls_usage">Solution Function</a> </li> |
| <li class="level1"> |
| <a href="#dls_opt_params">Optimizer Parameters</a> </li> |
| <li class="level1"> |
| <a href="#dls_examples">Examples</a> </li> |
| <li class="level1"> |
| <a href="#related">Related Topics</a> </li> |
| </ul> |
| </div><p>The linear systems module implements solution methods for systems of 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}\). We assume that there are no rows of \(A\) where all elements are zero. The algorithms implemented in this module can handle large dense linear systems. Currently, the algorithms implemented in this module solve the linear system by a direct decomposition. Hence, these methods are known as <em>direct method</em>.</p> |
| <p><a class="anchor" id="dls_usage"></a></p><dl class="section user"><dt>Solution Function</dt><dd><pre class="syntax"> |
| linear_solver_dense( tbl_source, |
| tbl_result, |
| row_id, |
| LHS, |
| RHS, |
| grouping_col, |
| optimizer, |
| optimizer_params |
| ) |
| </pre> <b>Arguments</b> <dl class="arglist"> |
| <dt>tbl_source </dt> |
| <dd><p class="startdd">TEXT. The name of the table containing the training data. The input data is expected to be of the following form: </p><pre>{TABLE|VIEW} <em>sourceName</em> ( |
| ... |
| <em>row_id</em> FLOAT8, |
| <em>left_hand_side</em> FLOAT8[], |
| <em>right_hand_side</em> FLOAT8, |
| ... |
| )</pre><p>Each row represents a single equation. The <em>right_hand_side</em> column refers to the right hand side of the equations while the <em>left_hand_side</em> column refers to the multipliers on the variables on the left hand side of the same equations.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>tbl_result </dt> |
| <dd><p class="startdd">TEXT. The name of the table where the output is saved. The output is stored in the table named by the <em>tbl_result</em> argument. It contains the following columns: </p><table class="output"> |
| <tr> |
| <th>solution </th><td>FLOAT8[]. The solution variables in the same order as that provided as input in the 'left_hand_side' column name of the <em>source_table</em> </td></tr> |
| <tr> |
| <th>residual_norm </th><td>FLOAT8. The scaled residual norm, defined as \( \frac{|Ax - b|}{|b|} \). This value is an indication of the accuracy of the solution. </td></tr> |
| <tr> |
| <th>iters </th><td>INTEGER. Number of iterations required by the algorithm (only applicable for iterative algorithms). The output is NULL for 'direct' methods. </td></tr> |
| </table> |
| <p class="enddd"></p> |
| </dd> |
| <dt>row_id </dt> |
| <dd><p class="startdd">TEXT. The name of the column storing the 'row id' of the equations.</p> |
| <p>For a system with N equations, the row_id's must be a continuous range of integers from \( 0 \ldots n-1 \). </p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>LHS </dt> |
| <dd><p class="startdd">TEXT. The name of the column storing the 'left hand side' of the equations, stored as an array.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>RHS </dt> |
| <dd><p class="startdd">TEXT. The name of the column storing the 'right hand side' of the equations.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>grouping_cols (optional) </dt> |
| <dd>TEXT, default: NULL. Group by column names. <em>Not currently implemented. Any non-NULL value is ignored.</em> </dd> |
| <dt>optimizer (optional) </dt> |
| <dd><p class="startdd">TEXT, default: 'direct'. The type of optimizer.</p> |
| <p class="enddd"></p> |
| </dd> |
| <dt>optimizer_params (optional) </dt> |
| <dd>TEXT, default: NULL. Optimizer specific parameters. </dd> |
| </dl> |
| </dd></dl> |
| <p><a class="anchor" id="dls_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: householderqr) </dt> |
| <dd><p class="startdd">There are several algorithms that can be classified as 'direct' methods of solving linear systems. MADlib dense linear system solvers provide various algorithmic options 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 | Conditions on A | Speed | Accuracy |
| ---------------------------------------------------------- |
| householderqr | None | ++ | + |
| partialpivlu | Invertable | ++ | + |
| fullpivlu | None | - | +++ |
| colpivhouseholderqr | None | + | ++ |
| fullpivhouseholderqr | None | - | +++ |
| llt | Pos. Definite | +++ | + |
| ldlt | Pos. or Neg Def | +++ | ++ |
| </pre><p>For speed '++' is faster than '+', which is faster than '-'. For accuracy '+++' is better than '++'.</p> |
| <p class="enddd">More details about the individual algorithms can be found in the <a href="http://eigen.tuxfamily.org/dox-devel/group__TutorialLinearAlgebra.html">Eigen documentation</a>. Eigen is an open source library for linear algebra. </p> |
| </dd> |
| </dl> |
| <p><a class="anchor" id="dls_examples"></a></p><dl class="section user"><dt>Examples</dt><dd></dd></dl> |
| <ol type="1"> |
| <li>View online help for the linear systems solver function. <pre class="example"> |
| SELECT madlib.linear_solver_dense(); |
| </pre></li> |
| <li>Create the sample data set. <pre class="example"> |
| CREATE TABLE linear_systems_test_data( id INTEGER NOT NULL, |
| lhs DOUBLE PRECISION[], |
| rhs DOUBLE PRECISION |
| ); |
| INSERT INTO linear_systems_test_data(id, lhs, rhs) |
| VALUES |
| (0, ARRAY[1,0,0], 20), |
| (1, ARRAY[0,1,0], 15), |
| (2, ARRAY[0,0,1], 20); |
| </pre></li> |
| <li>Solve the linear systems with default parameters. <pre class="example"> |
| SELECT madlib.linear_solver_dense( 'linear_systems_test_data', |
| 'output_table', |
| 'id', |
| 'lhs', |
| 'rhs' |
| ); |
| </pre></li> |
| <li>Obtain the output from the output table. <pre class="example"> |
| \x on |
| SELECT * FROM output_table; |
| </pre> Result: <pre class="result"> |
| --------------------+------------------------------------- |
| solution | {20,15,20} |
| residual_norm | 0 |
| iters | NULL |
| </pre></li> |
| <li>Choose an algorithm different than the default. <pre class="example"> |
| DROP TABLE IF EXISTS result_table; |
| SELECT madlib.linear_solver_dense( 'linear_systems_test_data', |
| 'result_table', |
| 'id', |
| 'lhs', |
| 'rhs', |
| NULL, |
| 'direct', |
| 'algorithm=llt' |
| ); |
| </pre></li> |
| </ol> |
| <p><a class="anchor" id="related"></a></p><dl class="section user"><dt>Related Topics</dt><dd>File <a class="el" href="dense__linear__systems_8sql__in.html" title="SQL functions for linear systems. ">dense_linear_systems.sql_in</a> documenting the SQL functions</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 Dec 15 2021 20:27:21 for MADlib by |
| <a href="http://www.doxygen.org/index.html"> |
| <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.13 </li> |
| </ul> |
| </div> |
| </body> |
| </html> |