linalg.sql_in

Go to the documentation of this file.

/* ----------------------------------------------------------------------- *//**
 *
 * @file linalg.sql_in
 *
 * @brief SQL functions for linear algebra
 *
 * @sa For an overview of linear-algebra functions, see the module
 *     description \ref grp_linalg.
 *
 *//* ----------------------------------------------------------------------- */

m4_include(`SQLCommon.m4')

/**
@addtogroup grp_linalg

\warning <em> This MADlib method is still in early stage development. There may be some 
issues that will be addressed in a future version. Interface and implementation
is subject to change. </em>

@about

The linalg module consists of useful utility functions for basic linear 
algebra operations. Several of these functions can be used
while implementing new algorithms.

Refer to the file for documentation on each of the utlity functions.


Linear-algebra functions.

@sa File linalg.sql_in documenting the SQL functions.
*/

/**
 * @brief 1-norm of a vector
 *
 * @param x Vector \f$ \vec x = (x_1, \dots, x_n) \f$
 * @return \f$ \| x \|_1 = \sum_{i=1}^n |x_i| \f$
 */
CREATE FUNCTION MADLIB_SCHEMA.norm1(
    x DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION
AS 'MODULE_PATHNAME'
LANGUAGE C
IMMUTABLE
STRICT;

/**
 * @brief 2-norm of a vector
 *
 * @param x Vector \f$ \vec x = (x_1, \dots, x_n) \f$
 * @return \f$ \| x \|_2 = \sqrt{\sum_{i=1}^n x_i^2} \f$
 */
CREATE FUNCTION MADLIB_SCHEMA.norm2(
    x DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION
AS 'MODULE_PATHNAME'
LANGUAGE C
IMMUTABLE
STRICT;

/**
 * @brief 1-norm of the difference between two vectors
 *
 * @param x Vector \f$ \vec x = (x_1, \dots, x_n) \f$
 * @param y Vector \f$ \vec y = (y_1, \dots, y_n) \f$
 * @return \f$ \| x - y \|_1 = \sum_{i=1}^n |x_i - y_i| \f$
 */
CREATE FUNCTION MADLIB_SCHEMA.dist_norm1(
    x DOUBLE PRECISION[],
    y DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION
AS 'MODULE_PATHNAME'
LANGUAGE C
IMMUTABLE
STRICT;

/**
 * @brief 2-norm of the difference between two vectors
 *
 * @param x Vector \f$ \vec x = (x_1, \dots, x_n) \f$
 * @param y Vector \f$ \vec y = (y_1, \dots, y_n) \f$
 * @return \f$ \| x - y \|_2 = \sqrt{\sum_{i=1}^n (x_i - y_i)^2} \f$
 */
CREATE FUNCTION MADLIB_SCHEMA.dist_norm2(
    x DOUBLE PRECISION[],
    y DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION
AS 'MODULE_PATHNAME'
LANGUAGE C
IMMUTABLE
STRICT;

/**
 * @brief Squared 2-norm of the difference between two vectors
 *
 * @param x Vector \f$ \vec x = (x_1, \dots, x_n) \f$
 * @param y Vector \f$ \vec y = (y_1, \dots, y_n) \f$
 * @return \f$ \| x - y \|_2^2 = \sum_{i=1}^n (x_i - y_i)^2 \f$
 */
CREATE FUNCTION MADLIB_SCHEMA.squared_dist_norm2(
    x DOUBLE PRECISION[],
    y DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION
AS 'MODULE_PATHNAME'
LANGUAGE C
IMMUTABLE
STRICT;

/**
 * @brief Angle between two vectors
 *
 * @param x Vector \f$ \vec x = (x_1, \dots, x_n) \f$
 * @param y Vector \f$ \vec y = (y_1, \dots, y_n) \f$
 * @return \f$ \arccos\left(\frac{\langle \vec x, \vec y \rangle}
 *                               {\| \vec x \| \cdot \| \vec y \|}\right) \f$
 */
CREATE FUNCTION MADLIB_SCHEMA.dist_angle(
    x DOUBLE PRECISION[],
    y DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION
AS 'MODULE_PATHNAME'
LANGUAGE C
IMMUTABLE
STRICT;

/**
 * @brief Tanimoto distance between two vectors
 *
 * @param x Vector \f$ \vec x = (x_1, \dots, x_n) \f$
 * @param y Vector \f$ \vec y = (y_1, \dots, y_n) \f$
 * @return \f$ 1 - \frac{\langle \vec x, \vec y \rangle}
 *                            {\| \vec x \|^2 \cdot \| \vec y \|^2
 *                                - \langle \vec x, \vec y \rangle} \f$
 */
CREATE FUNCTION MADLIB_SCHEMA.dist_tanimoto(
    x DOUBLE PRECISION[],
    y DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION
AS 'MODULE_PATHNAME'
LANGUAGE C
IMMUTABLE
STRICT;

/*
 * @brief closest_column return type
 */
CREATE TYPE MADLIB_SCHEMA.closest_column_result AS (
    column_id INTEGER,
    distance DOUBLE PRECISION
);

/**
 * @brief Given matrix \f$ M \f$ and vector \f$ \vec x \f$ compute the column
 *     of \f$ M \f$ that is closest to \f$ \vec x \f$
 *
 * @param M Matrix \f$ M = (\vec{m_0} \dots \vec{m_{l-1}})
 *     \in \mathbb{R}^{k \times l} \f$
 * @param x Vector \f$ \vec x \in \mathbb R^k \f$
 * @param dist The metric \f$ \operatorname{dist} \f$. This needs to be a
 *     function with signature
 *     <tt>DOUBLE PRECISION[] x DOUBLE PRECISION[] -> DOUBLE PRECISION</tt>.
 *
 * @returns A composite value:
 *  - <tt>columns_id INTEGER</tt> - The 0-based index of the column of \f$ M \f$
 *     that is closest to \f$ x \f$. In case of ties, the first such index is
 *     returned. That is, \c columns_id is the minimum element in the set
 *     \f$ \arg\min_{i=0,\dots,l-1} \operatorname{dist}(\vec{m_i}, \vec x) \f$.
 *  - <tt>distance DOUBLE PRECISION</tt> - The minimum distance between any
 *     column of \f$ M \f$ and \f$ x \f$. That is,
 *     \f$ \min_{i=0,\dots,l-1} \operatorname{dist}(\vec{m_i}, \vec x) \f$.
 */
CREATE FUNCTION MADLIB_SCHEMA.closest_column(
    M DOUBLE PRECISION[][],
    x DOUBLE PRECISION[],
    dist REGPROC /*+ DEFAULT 'squared_dist_norm2' */
) RETURNS MADLIB_SCHEMA.closest_column_result
IMMUTABLE
STRICT
LANGUAGE C
AS 'MODULE_PATHNAME';

CREATE FUNCTION MADLIB_SCHEMA.closest_column(
    M DOUBLE PRECISION[][],
    x DOUBLE PRECISION[]
) RETURNS MADLIB_SCHEMA.closest_column_result
IMMUTABLE
STRICT
LANGUAGE sql
AS $$
    SELECT MADLIB_SCHEMA.closest_column($1, $2,
        'MADLIB_SCHEMA.squared_dist_norm2')
$$;

/*
 * @brief closest_columns return type
 */
CREATE TYPE MADLIB_SCHEMA.closest_columns_result AS (
    column_ids INTEGER[],
    distances DOUBLE PRECISION[]
);

/**
 * @brief Given matrix \f$ M \f$ and vector \f$ \vec x \f$ compute the columns
 *     of \f$ M \f$ that are closest to \f$ \vec x \f$
 *
 * This function does essentially the same as \ref closest_column(), except that
 * it allows to specify the number of closest columns to return. The return
 * value is a composite value:
 *  - <tt>columns_ids INTEGER[]</tt> - The 0-based indices of the \c num columns
 *     of \f$ M \f$ that are closest to \f$ x \f$. In case of ties, the first
 *     such indices are returned.
 *  - <tt>distances DOUBLE PRECISION[]</tt> - The distances between the columns
 *     of \f$ M \f$ with indices in \c columns_ids and \f$ x \f$. That is,
 *     <tt>distances[i]</tt> contains
 *     \f$ \operatorname{dist}(\vec{m_j}, \vec x) \f$, where \f$ j = \f$
 *     <tt>columns_ids[i]</tt>.
 */
CREATE FUNCTION MADLIB_SCHEMA.closest_columns(
    M DOUBLE PRECISION[][],
    x DOUBLE PRECISION[],
    num INTEGER,
    dist REGPROC /*+ DEFAULT 'squared_dist_norm2' */
) RETURNS MADLIB_SCHEMA.closest_columns_result
IMMUTABLE
STRICT
LANGUAGE C
AS 'MODULE_PATHNAME';

CREATE FUNCTION MADLIB_SCHEMA.closest_columns(
    M DOUBLE PRECISION[][],
    x DOUBLE PRECISION[],
    num INTEGER
) RETURNS MADLIB_SCHEMA.closest_columns_result
IMMUTABLE
STRICT
LANGUAGE sql
AS $$
    SELECT MADLIB_SCHEMA.closest_columns($1, $2, $3,
        'MADLIB_SCHEMA.squared_dist_norm2')
$$;

CREATE FUNCTION MADLIB_SCHEMA.avg_vector_transition(
    state DOUBLE PRECISION[],
    x DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION[]
LANGUAGE c
IMMUTABLE
CALLED ON NULL INPUT
AS 'MODULE_PATHNAME';

CREATE FUNCTION MADLIB_SCHEMA.avg_vector_merge(
    state_left DOUBLE PRECISION[],
    state_right DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION[]
LANGUAGE c
IMMUTABLE
STRICT
AS 'MODULE_PATHNAME';

CREATE FUNCTION MADLIB_SCHEMA.avg_vector_final(
    state DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION[]
LANGUAGE c
IMMUTABLE
STRICT
AS 'MODULE_PATHNAME';

/**
 * @brief Compute the average of vectors
 *
 * Given vectors \f$ x_1, \dots, x_n \f$, compute the average
 * \f$ \frac 1n \sum_{i=1}^n x_i \f$.
 *
 * @param x Point \f$ x_i \f$
 * @returns Average \f$ \frac 1n \sum_{i=1}^n x_i \f$
 */
CREATE AGGREGATE MADLIB_SCHEMA.avg(
    /*+ x */ DOUBLE PRECISION[]
) (
    STYPE=DOUBLE PRECISION[],
    SFUNC=MADLIB_SCHEMA.avg_vector_transition,
    m4_ifdef(`__GREENPLUM__', `PREFUNC=MADLIB_SCHEMA.avg_vector_merge,')
    FINALFUNC=MADLIB_SCHEMA.avg_vector_final,
    INITCOND='{0,0,0}'
);

CREATE FUNCTION MADLIB_SCHEMA.normalized_avg_vector_transition(
    state DOUBLE PRECISION[],
    x DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION[]
LANGUAGE c
IMMUTABLE
CALLED ON NULL INPUT
AS 'MODULE_PATHNAME';

CREATE FUNCTION MADLIB_SCHEMA.normalized_avg_vector_final(
    state DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION[]
LANGUAGE c
IMMUTABLE
STRICT
AS 'MODULE_PATHNAME';

/**
 * @brief Compute the normalized average of vectors
 *
 * Given vectors \f$ x_1, \dots, x_n \f$, define
 * \f$ \widetilde{x} := \frac 1n \sum_{i=1}^n \frac{x_i}{\| x_i \|} \f$, and
 * compute the normalized average
 * \f$ \frac{\widetilde{x}}{\| \widetilde{x} \|} \f$.
 *
 * @param x Point \f$ x_i \f$
 * @returns Normalized average \f$ \frac{\widetilde{x}}{\| \widetilde{x} \|} \f$
 */
CREATE AGGREGATE MADLIB_SCHEMA.normalized_avg(
    /*+ x */ DOUBLE PRECISION[]
) (
    STYPE=DOUBLE PRECISION[],
    SFUNC=MADLIB_SCHEMA.normalized_avg_vector_transition,
    m4_ifdef(`__GREENPLUM__', `PREFUNC=MADLIB_SCHEMA.avg_vector_merge,')
    FINALFUNC=MADLIB_SCHEMA.normalized_avg_vector_final,
    INITCOND='{0,0,0}'
);

CREATE FUNCTION MADLIB_SCHEMA.matrix_agg_transition(
    state DOUBLE PRECISION[],
    x DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION[]
LANGUAGE c
IMMUTABLE
STRICT
AS 'MODULE_PATHNAME';

CREATE FUNCTION MADLIB_SCHEMA.matrix_agg_final(
    state DOUBLE PRECISION[]
) RETURNS DOUBLE PRECISION[]
LANGUAGE c
IMMUTABLE
STRICT
AS 'MODULE_PATHNAME';

/**
 * @brief Combine vectors to a matrix
 *
 * Given vectors \f$ \vec x_1, \dots, \vec x_n \in \mathbb R^m \f$,
 * return matrix \f$ ( \vec x_1 \dots \vec x_n ) \in \mathbb R^{m \times n}\f$.
 *
 * @param x Vector \f$ x_i \f$
 * @returns Matrix with columns \f$ x_1, \dots, x_n \f$
 */
CREATE
m4_ifdef(`__GREENPLUM__', m4_ifdef(`__HAS_ORDERED_AGGREGATES__', `ORDERED'))
AGGREGATE MADLIB_SCHEMA.matrix_agg(
    /*+ x */ DOUBLE PRECISION[]
) (
    STYPE=DOUBLE PRECISION[],
    SFUNC=MADLIB_SCHEMA.matrix_agg_transition,
    FINALFUNC=MADLIB_SCHEMA.matrix_agg_final,
    INITCOND='{0,0,0}'
);

/**
 * @brief Return the column of a matrix
 *
 * @param matrix Two-dimensional matrix
 * @param col Column of the matrix to return (0-based index)
 */
CREATE FUNCTION MADLIB_SCHEMA.matrix_column(
    matrix DOUBLE PRECISION[][],
    col INTEGER
) RETURNS DOUBLE PRECISION[]
LANGUAGE c
IMMUTABLE
STRICT
AS 'MODULE_PATHNAME';