linAlg.h File Reference

#include "scs.h"
#include <math.h>

Go to the source code of this file.

Functions
scs_int	scs_svd_workspace_size (scs_int m, scs_int n)
	Computes the optimal workspace size for scs_svdls. More...
scs_int	scs_qr_workspace_size (scs_int m, scs_int n)
	Compute the optimal size of workspace for scs_qrls. More...
scs_int	scs_qrls (scs_int m, scs_int n, scs_float *RESTRICT A, scs_float *RESTRICT b, scs_float *RESTRICT wspace, scs_int wsize)
	Solves a least squares problem using the QR factorization. More...
scs_int	scs_svdls (scs_int m, scs_int n, scs_float *RESTRICT A, scs_float *RESTRICT b, scs_float *RESTRICT wspace, scs_int wsize, scs_float rcond, scs_float *RESTRICT singular_values, scs_int *RESTRICT rank)
	Solves a least squares problem using the SVD factorization. More...
void	scs_set_as_scaled_array (scs_float *RESTRICT x, const scs_float *RESTRICT a, const scs_float b, scs_int len)
void	scs_scale_array (scs_float *RESTRICT a, const scs_float b, scs_int len)
scs_float	scs_inner_product (const scs_float *RESTRICT x, const scs_float *RESTRICT y, scs_int len)
scs_float	scs_norm_squared (const scs_float *RESTRICT v, scs_int len)
scs_float	scs_norm (const scs_float *RESTRICT v, scs_int len)
scs_float	scs_norm_infinity (const scs_float *RESTRICT a, scs_int l)
void	scs_add_scaled_array (scs_float *RESTRICT a, const scs_float *RESTRICT b, scs_int n, const scs_float sc)
void	scs_add_array (scs_float *RESTRICT a, const scs_float *RESTRICT b, scs_int n)
void	scs_axpy (scs_float *RESTRICT x, const scs_float *RESTRICT u, const scs_float *RESTRICT v, scs_float a, scs_float b, scs_int n)
void	scs_subtract_array (scs_float *RESTRICT a, const scs_float *RESTRICT b, scs_int n)
scs_float	scs_norm_difference (const scs_float *RESTRICT a, const scs_float *RESTRICT b, scs_int l)
scs_float	scs_norm_infinity_difference (const scs_float *RESTRICT a, const scs_float *RESTRICT b, scs_int l)
void	scs_matrix_multiply (scs_int rows_A, scs_int cols_B, scs_int cols_A, scs_float alpha, const scs_float *RESTRICT A, scs_float beta, const scs_float *RESTRICT B, scs_float *C)
void	scs_matrix_transpose_multiply (scs_int rows_A, scs_int cols_B, scs_int cols_A, scs_float alpha, const scs_float *RESTRICT A, scs_float beta, const scs_float *RESTRICT B, scs_float *C)
scs_float *	scs_cgls_malloc_workspace (scs_int m, scs_int n)
scs_int	scs_cgls (scs_int m, scs_int n, const scs_float *RESTRICT A, const scs_float *RESTRICT b, scs_float *RESTRICT x, scs_float tol, scs_int *RESTRICT maxiter, scs_float *RESTRICT wspace)

Function Documentation

void scs_add_array	(	scs_float *RESTRICT	a,
		const scs_float *RESTRICT	b,
		scs_int	n
	)

Performs the operation

\[ a \leftarrow a + b \]

Parameters

a	vector a
b	vector b
n	length of a

Note

with loop unrolling for speed

void scs_add_scaled_array	(	scs_float *RESTRICT	a,
		const scs_float *RESTRICT	b,
		scs_int	n,
		const scs_float	sc
	)

Performs the operation

\[ a \leftarrow a + \gamma b \]

Parameters

a	vector a
b	vector b
n	length of a
sc	the scalar \(\gamma\)

Note

with loop unrolling for speed

void scs_axpy	(	scs_float *RESTRICT	x,
		const scs_float *RESTRICT	u,
		const scs_float *RESTRICT	v,
		scs_float	a,
		scs_float	b,
		scs_int	n
	)

Computes \(x \leftarrow \alpha u + \beta v\)

Note

The pointer x can have the same value as u so as to perform operations like \(x\leftarrow \alpha x + \beta v\).

scs_int scs_cgls	(	scs_int	m,
		scs_int	n,
		const scs_float *RESTRICT	A,
		const scs_float *RESTRICT	b,
		scs_float *RESTRICT	x,
		scs_float	tol,
		scs_int *RESTRICT	maxiter,
		scs_float *RESTRICT	wspace
	)

Solves a least squares problem using the conjugate gradient method.

Solves the problem: Minimize \(\|Ax-b\|^2\), or, what is the same, the linear system \( A^{\top}Ax = A^{\top}b\).

The iterations are terminated when the Euclidean norm of the residual, \(r = A^{\top}(b - Ax)\) becomes smaller than the specified tolerance.

Parameters

m	Number of rows of matrix A
n	Number of columns of A
A	Matrix A (column-packed)
b	Right-hand side vector b
x	Solution (on entry: initial guess)
tol	Tolerance
maxiter	Maximum number of CG iterations (on exit: number of iterations)
wspace	Externally allocated memory space serving as workspace. This must be of size (max(m,n) + m + 2 * n) * sizeof(scs_float). On exit, the first n memory positions store the residual. You may use scs_cgls_malloc_workspace to allocate the workspace.

Returns

status code (0: success, 1: maximum number of iterations reached).

See Also

scs_cgls_malloc_workspace

scs_float* scs_cgls_malloc_workspace	(	scs_int	m,
		scs_int	n
	)

Allocates memory to be used as workspace in scs_cgls (see documentation of scs_cgls for details).

If either m or n are negative or zero, it returns SCS_NULL.

Note

The caller should always check whether the returned pointer is SCS_NULL.

Warning

The caller should free the memory allocated by this function. Example:

scs_int m = 10;
scs_int n = 2;
scs_float * ws;
ws = scs_cgls_malloc_workspace(scs_int m, scs_int n);
if (ws == SCS_NULL) {
     // memory not allocated, take necessary action
}
// use ws in cgls
scs_free(ws);

Parameters

m	number of rows of matrix A
n	number of columns of matrix A

Returns

pointer to allocated

See Also

scs_cgls

scs_float scs_inner_product	(	const scs_float *RESTRICT	x,
		const scs_float *RESTRICT	y,
		scs_int	len
	)

Computes the inner product of two vectors, that is

\[ \langle x, y \rangle = x'y = \sum_{i=1}^{\mathrm{len}}x_i y_i. \]

Parameters

x	vector \(x\)
y	vector \(y\)
len	length of vectors

Returns

inner product of \(x\) with \(y\)

void scs_matrix_multiply	(	scs_int	rows_A,
		scs_int	cols_B,
		scs_int	cols_A,
		scs_float	alpha,
		const scs_float *RESTRICT	A,
		scs_float	beta,
		const scs_float *RESTRICT	B,
		scs_float *	C
	)

Perofrms the operation \(C \leftarrow \beta C + \alpha A B,\) where \(A\), \(B\) and \(C\) are column-packed matrices.

Parameters

rows_A	number of rows of matrix \(A\)
cols_B	number of columns of matrix \(B\)
cols_A	number of rows of matrix \(B\) (columns of \(A\))
alpha	coefficient \(\alpha\)
A	pointer to matrix \(A\) in column-packed form
beta	coefficient \(\beta\)
B	pointer to matrix \(B\) in column-packed form
C	pointer to matrix \(C\) in column-packed form

void scs_matrix_transpose_multiply	(	scs_int	rows_A,
		scs_int	cols_B,
		scs_int	cols_A,
		scs_float	alpha,
		const scs_float *RESTRICT	A,
		scs_float	beta,
		const scs_float *RESTRICT	B,
		scs_float *	C
	)

Perofrms the operation \(C \leftarrow \beta C + \alpha A^{\top} B,\) where \(A\), \(B\) and \(C\) are column-packed matrices.

Parameters

rows_A	number of rows of matrix \(A\)
cols_B	number of columns of matrix \(B\)
cols_A	number of rows of matrix \(B\) (columns of \(A\))
alpha	coefficient \(\alpha\)
A	pointer to matrix \(A\) in column-packed form
beta	coefficient \(\beta\)
B	pointer to matrix \(B\) in column-packed form
C	pointer to matrix \(C\) in column-packed form

scs_float scs_norm	(	const scs_float *RESTRICT	v,
		scs_int	len
	)

Returns the Euclidean norm of a vector.

Parameters

v
len

Returns

scs_float scs_norm_difference	(	const scs_float *RESTRICT	a,
		const scs_float *RESTRICT	b,
		scs_int	l
	)

Returns the Euclidean norm of the difference of two vectors

Parameters

a
b
l

Returns

scs_float scs_norm_infinity	(	const scs_float *RESTRICT	a,
		scs_int	l
	)

Returns the infinity norm of a vector.

Parameters

a
l

Returns

scs_float scs_norm_infinity_difference	(	const scs_float *RESTRICT	a,
		const scs_float *RESTRICT	b,
		scs_int	l
	)

Returns the infinity norm of the difference of two vectors

Parameters

a
b
l

Returns

scs_float scs_norm_squared	(	const scs_float *RESTRICT	v,
		scs_int	len
	)

Returns the square Euclidean norm of a vector \(v\).

Parameters

v	vector \(v\)
len	length of vector

Returns

norm of vector \(v\)

Note

uses scs_inner_product

scs_int scs_qr_workspace_size	(	scs_int	m,
		scs_int	n
	)

Compute the optimal size of workspace for scs_qrls.

Parameters

m	rows of A
n	columns of A

Returns

optimal size of workspace

Note

To use this function, you need to compile with USE_LAPACK=1 (recommended).

scs_int scs_qrls	(	scs_int	m,
		scs_int	n,
		scs_float *RESTRICT	A,
		scs_float *RESTRICT	b,
		scs_float *RESTRICT	wspace,
		scs_int	wsize
	)

Solves a least squares problem using the QR factorization.

Parameters

m	rows of A
n	columns of A
A	On entry, matrix A (column-packed). On exit, if \(m\geq n\), A is overwritten by details of its QR factorization as returned by lapack's DGEQRF; otherwise, A is overwritten by details of its LQ factorization as returned by DGELQF.
b	On entry: vector b, On exit: solution
wspace	workspace
wsize	workspace size

Returns

status code (0: success)

See Also

scs_qr_workspace_size

Note

This is a wrapper for lapack's ?gels

Warning

It is assumed that matrix \(A\) has full rank. If not, use scs_svdls.

Note

To use this function, you need to compile with USE_LAPACK=1 (recommended).

void scs_scale_array	(	scs_float *RESTRICT	a,
		const scs_float	b,
		scs_int	len
	)

Performs the operation

\[ a \leftarrow b\cdot a \]

Parameters

a	vector \(a\)
b	vector \(b\)
len	length of vectors

void scs_set_as_scaled_array	(	scs_float *RESTRICT	x,
		const scs_float *RESTRICT	a,
		const scs_float	b,
		scs_int	len
	)

Performs the operation

\[ x \leftarrow b\cdot a, \]

where a is a vector and b is a scalar.

Parameters

x
a
b
len

Note

with loop unrolling for speed

void scs_subtract_array	(	scs_float *RESTRICT	a,
		const scs_float *RESTRICT	b,
		scs_int	n
	)

Performs the operation

\[ a \leftarrow a - b \]

Parameters

a	vector a
b	vector b
n	length of a

Note

with loop unrolling for speed

scs_int scs_svd_workspace_size	(	scs_int	m,
		scs_int	n
	)

Computes the optimal workspace size for scs_svdls.

Parameters

m	number of rows of matrix A
n	number of columns of matrix A

Returns

optimal workspace size

Note

To use this function, you need to compile with USE_LAPACK=1 (recommended).

scs_int scs_svdls	(	scs_int	m,
		scs_int	n,
		scs_float *RESTRICT	A,
		scs_float *RESTRICT	b,
		scs_float *RESTRICT	wspace,
		scs_int	wsize,
		scs_float	rcond,
		scs_float *RESTRICT	singular_values,
		scs_int *RESTRICT	rank
	)

Solves a least squares problem using the SVD factorization.

Solves the least squares problem \(\mathrm{Minimize}\|b-Ax\|^2\) where \(A\in\mathbb{R}^{m\times n}\) and \(b\in\mathbb{R}^{m}\).

Parameters

m	number of rows of matrix A
n	number of columns of matrix A
A	On entry, matrix A. On exit, the first min(m,n) rows of A are overwritten with its right singular vectors, stored row-wise.
b	On entry, vector b, On exit, solution
wspace	workspace
wsize	size of the workspace (its size is returned by scs_svd_workspace_size)
rcond	rcond is used to determine the effective rank of A. singular values \( \sigma_i \leq \mathrm{rcond} \cdot \sigma_1\) are treated as zero.
singular_values	this function computes the singular values of \(A\)
rank	the effective rank of matrix \(A\), that is, the number of singular values which are greater than \(\mathrm{rcond} \cdot \sigma_1\).

Returns

status (0: success)

Note

This is a wrapper for lapack's ?gelss.

To use this function, you need to compile with USE_LAPACK=1 (recommended).