Sparse Linear Systems

Collaboration diagram for Sparse Linear Systems:

Contents

• About
• Online Help
• Function Syntax
• Arguments
• Optimizer Parameters
• Output Tables
• Examples

About:

The sparse linear systems module implements solution methods for systems of a consistent linear equations. Systems of linear equations take the form:

\[ Ax = b \]

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.

Note

Algorithms with fail if there is an row of the input matrix containing all zeros.

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.

Online Help

View short help messages using the following statements:

-- 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');

Syntax

linear_solver_sparse(tbl_source_lhs, tbl_source_rhs, tbl_result,
                     row_id, LHS, RHS, grouping_cols := NULL,
                     optimizer := 'direct',
                     optimizer_params := 'algorithm = llt');

Arguments

LHS

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:

{TABLE|VIEW} sourceName (
    ...
    row_id FLOAT8,
    col_id FLOAT8,
    value FLOAT8,
    ...
)

Here, each row represents a single equation using. The rhs refers to the right hand side of the equations while the lhs refers to the multipliers on the variables on the left hand side of the same equations.

RHS

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:

{TABLE|VIEW} sourceName (
    ...
    row_id FLOAT8,
    value FLOAT8
    ...
)

Here, each row represents a single equation using. The rhs refers to the right hand side of the equations while the lhs refers to the multipliers on the variables on the left hand side of the same equations.

Output is stored in the tbl_result

    tbl_result      |   Data Types
--------------------|---------------------
solution            | DOUBLE PRECISION[]
residual_norm       | DOUBLE PRECISIOn
iters               | INTEGER

Syntax

SELECT sparse_linear_sytems('tbl_source_lhs', 'tbl_source_rhs', 'tbl_result',
                'row_id', 'LHS', 'RHS', NULL, 'direct', 'algorithm = householderqr');

tbl_source_lhs

Text value. The name of the table containing the LHS matrix.

tbl_source_rhs

Text value. The name of the table containing the RHS vector.

tbl_result

Text value. The name of the table where the output is saved.

lhs_row_id

Text value. The name of the column storing the 'row id' of the equations.

Note

For a system with N equations, the row_id's must be a continuous range of integers from \( 0 \ldots n-1 \).

lhs_col_id

Text value. The name of the column (in tbl_source_lhs) storing the 'col id' of the equations.

lhs_value

Text value. The name of the column (in tbl_source_lhs) storing the 'value' of the equations.

rhs_row_id

Text value. The name of the column (in tbl_source_rhs) storing the 'col id' of the equations.

rhs_value

Text value. The name of the column (in tbl_source_rhs) storing the 'value' of the equations.

num_vars

Integer value. The number of variables in the linear system. equations.

grouping_col (optional)

Text value. Group by columns. Default: NULL.

Note

The grouping columns is a placeholder in MADlib V1.1

optimizer (optional)

Text value. Type of optimizer. Default: 'direct'.

optimizer_params (optional)

Text value. Optimizer specific parameters. Default: NULL.

Optimizer Parameters

For each optimizer, there are specific parameters that can be tuned for better performance.

algorithm (default: ldlt)

There are several algorithms that can be classified as 'direct' methods of solving linear systems. Madlib functions provide various algorithmic options available for users.

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.

Algorithm          | Contitions on A  | Speed | Memory
----------------------------------------------------------
llt                | Sym. Pos Def     |  ++   |  ---
ldlt               | Sym. Pos Def     |  ++   |  ---

For speed '++' is faster than '+', which is faster than '-'. For accuracy '+++' is better than '++'. For memory, '-' uses less memory than '–'.

Note: ldlt is often preferred over llt

There are several algorithms that can be classified as 'iterative' methods of solving linear systems. Madlib functions provide various algorithmic options available for users.

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.

  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 '+'.

Details:

1. cg-mem: In memory conjugate gradient with diagonal preconditioners.
2. bicgstab-mem: Bi-conjugate gradient (equivalent to performing CG on the least squares formulation of Ax=b) with incomplete LU preconditioners.
3. precond-cg-mem: In memory conjugate gradient with diagonal preconditioners.
4. bicgstab-mem: Bi-conjugate gradient (equivalent to performing CG on the least squares formulation of Ax=b) with incomplete LU preconditioners.

toler (default: 1e-5)

Termination tolerance (applicable only for iterative methods) which determines the stopping criterion (with respect to residual norm) for iterative methods.

Output statistics

solution

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'

residual_norm

Computes the scaled residual norm, defined as \( \frac{|Ax - b|}{|b|} \) gives the user an indication of the accuracy of the solution.

iters

The number of iterations required by the algorithm (only applicable for iterative algorithms) . The output is NULL for direct' methods.

Examples:

1. Create the sample data set:

   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);
   

2. Solve the linear systems with default parameters

   sql> SELECT madlib.linear_solver_sparse(
                                    'sparse_linear_systems_lhs',
                                    'sparse_linear_systems_rhs',
                                    'output_table',
                                    'rid',
                                    'cid',
                                    'val',
                                    'rid',
                                    'val',
                                    4);
   

3. Obtain the output from the output table

   sql> SELECT * FROM output_table;
   --------------------+-------------------------------------
   solution            | {10,20,30,0}
   residual_norm       | 0
   iters               | NULL
   

4. Chose a different algorithm than the default algorithm

   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');
   

See Also

File sparse_linear_sytems.sql_in documenting the SQL functions.