Complexity Concept

Actually all expressions have their algorithmic complexity.

In context of this library complexity of an operation means an estimation of it's algorithmic complexity.

For example imagine we are adding two vectors. That means we add together corresponding elements of these vectors and thus we get the resulting vector. Number of sums is equal to initial vectors' size, i.e. n. Thus we can speak about linear complexity because our effort for computing result are growing linearly in size of the initial vectors. In so called "big O" notation we have an O(n) complexity.

Expressions have the following complexity values:

• 0 represents O(n⁰) complexity that is constant complexity (O(1)), typically actual storage types and reference types has constant complexity, entities which do not involve computations but only refer to other storage types;
• 1 represents O(n¹) complexity that is linear complexity (O(n)), expressions like addition of two vectors or multiplication of a vector by a scalar have linear complexity (due to limitations some other things fall here, e.g. linear logarithmic (O(n log n)) complexity; keep this in mind while defining your own expressions);
• 2 represents O(n²) complexity that is square complexity, expressions like addition of two matrices or a multiplication of a matrix by a vector has square complexity;
• 3 represents O(n³) complexity that is cubic complexity, multiplication of two matrices has cubic complexity.

All these values are conventional of course.

This information is very useful to decide what to do with objects provided by reference: copy the result to a temporary or to use "as is", whichever seems to be faster. For example imagine a function which has to perform some operation getting a reference to an expression. If the operation refers to each element of the source expression only once then there is no need to store the result of expression evaluation to a temporary storage. Even if the expression has high complexity copying the result to temporary is not necessary. The different case is when the operation needs the value of an arbitrary element several times during a computation. If the complexity of the source expression is higher than constant value (i.e. O(1)) then sequential computations of same element will bring nothing but sorrow. Instead, the result of the source expression must be saved in a temporary and then used with much less overal performance penalty.

There is a rule for "big O" arithmetic: if you add two values then the dominating one wins, i.e.
O(n^a) + O(n^b) equates to O(n^{max(a, b)}).
Another example:
O(n) + O(n log n) equates to O(n log n)
(because (n log n) dominates over n).

It also applies to matrix and vector expressions: if an expresion with complexity O(n^a) is a subexpression of an expression with complexity O(n^b) then the actual complexity of the whole composite expression is O(n^{max(a, b)}).

The same applies to binary expressions:
bin_expression(O(n^a))( expression1(O(n^b)), expression2(O(n^c) )
actually has complexity O(n^a) + O(n^b) + O(n^c) which equates to O(n^{max(a, b, c)}).

For example imagine two matrices n by n elements each are multiplied. That is an O(n³) operation. Then it need to be transposed. Generally speaking a transposition is an O(1) operation because one only needs to swap indeces of elements. But a transposition of a matrix multiplication has algorithmic complexity O(n³).

Consider complexitiy of different expressions (m denotes a matrix, v denotes a vector and s denotes a scalar value):

Member nabla::conj (const matrix_expression< value_t, expr_t, tag > &a)

conj(m): algorithmic complexity of this operation is constant (i.e. O(1)).

Member nabla::conj (const matrix_expression< value_t, expr_t, tag > &a)

conj(m): algorithmic complexity of this operation is constant (i.e. O(1)).

Member nabla::conj (const vector_expression< value_t, expr_t, tag > &a)

conj(v): algorithmic complexity of this operation is constant (i.e. O(1)).

Member nabla::conj (const vector_expression< value_t, expr_t, tag > &a)

conj(v): algorithmic complexity of this operation is constant (i.e. O(1)).

Member nabla::div (const vector_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2 > &right)

div(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::div (const vector_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2 > &right)

div(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::div (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

mul(m, m): algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::div (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

mul(m, m): algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::dot_product (const vector_expression< value_t, expr1, tag1 > &v1, const vector_expression< value_t, expr2, tag2 > &v2)

dot_product(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::dot_product (const vector_expression< value_t, expr1, tag1 > &v1, const vector_expression< value_t, expr2, tag2 > &v2)

dot_product(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::map (const matrix_expression< value_t, expr1, tag1 > &linear_map, const vector_expression< value_t, expr2, tag2 > &v)

map(m, v): algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::map (const matrix_expression< value_t, expr1, tag1 > &linear_map, const vector_expression< value_t, expr2, tag2 > &v)

map(m, v): algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::mul (const vector_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2 > &right)

mul(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::mul (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

mul(m, m): algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::mul (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

mul(m, m): algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::mul (const vector_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2 > &right)

mul(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::norm (const vector_expression< value_t, expr_t, tag > &v)

norm(v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::norm (const vector_expression< value_t, expr_t, tag > &v)

norm(v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator* (const matrix_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2, orientation::column > &right)

m*v: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator* (const vector_expression< value_t, expr_t, tag > &a, const typename expr_t::value_type &s)

v*s: algorithmic complexity of this operation is linear (i.e.

Member nabla::operator* (const typename expr_t::value_type &s, const vector_expression< value_t, expr_t, tag > &a)

s*v: algorithmic complexity of this operation is linear (i.e.

Member nabla::operator* (const matrix_expression< value_t, expr_t, tag > &a, const typename expr_t::value_type &s)

m*s: algorithmic complexity of this operation is square (i.e.

Member nabla::operator* (const matrix_expression< value_t, expr_t, tag > &a, const typename expr_t::value_type &s)

m*s: algorithmic complexity of this operation is square (i.e.

Member nabla::operator* (const typename expr_t::value_type &s, const matrix_expression< value_t, expr_t, tag > &a)

s*m: algorithmic complexity of this operation is square (i.e.

Member nabla::operator* (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m*m: algorithmic complexity of this operation is cubic (i.e. O(n³)).

Member nabla::operator* (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m*m: algorithmic complexity of this operation is cubic (i.e. O(n³)).

Member nabla::operator* (const matrix_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2, orientation::column > &right)

m*v: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator* (const vector_expression< value_t, expr_t, tag > &a, const typename expr_t::value_type &s)

v*s: algorithmic complexity of this operation is linear (i.e.

Member nabla::operator* (const typename expr_t::value_type &s, const vector_expression< value_t, expr_t, tag > &a)

s*v: algorithmic complexity of this operation is linear (i.e.

Member nabla::operator* (const typename expr_t::value_type &s, const matrix_expression< value_t, expr_t, tag > &a)

s*m: algorithmic complexity of this operation is square (i.e.

Member nabla::operator*= (vector_expression< value_t, expr_t, tag::reference > &left, const value_t &right)

v *= s: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator*= (matrix_expression< value_t, expr1, tag::storage > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m *= m: algorithmic complexity of this operation is cubic (i.e. O(n³)).

Member nabla::operator*= (vector_expression< value_t, expr_t, tag::storage > &left, const value_t &right)

v *= s: algorithmic complexity of this operation is linear (i.e.

Member nabla::operator*= (vector_expression< value_t, expr_t, tag::reference > &left, const value_t &right)

v *= s: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator*= (vector_expression< value_t, expr_t, tag::storage > &left, const value_t &right)

v *= s: algorithmic complexity of this operation is linear (i.e.

Member nabla::operator*= (matrix_expression< value_t, expr_t, tag::storage > &left, const value_t &right)

m *= s: algorithmic complexity of this operation is square (i.e.

Member nabla::operator*= (matrix_expression< value_t, expr1, tag::storage > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m *= m: algorithmic complexity of this operation is cubic (i.e. O(n³)).

Member nabla::operator*= (matrix_expression< value_t, expr_t, tag::storage > &left, const value_t &right)

m *= s: algorithmic complexity of this operation is square (i.e.

Member nabla::operator+ (const vector_expression< value_t, expr_t, tag > &a)

+v: algorithmic complexity of this operation is constant (i.e.

Member nabla::operator+ (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m + m: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator+ (const vector_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2 > &right)

v + v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator+ (const vector_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2 > &right)

v + v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator+ (const matrix_expression< value_t, expr_t, tag > &a)

+m: algorithmic complexity of this operation is constant (i.e.

Member nabla::operator+ (const matrix_expression< value_t, expr_t, tag > &a)

+m: algorithmic complexity of this operation is constant (i.e.

Member nabla::operator+ (const vector_expression< value_t, expr_t, tag > &a)

+v: algorithmic complexity of this operation is constant (i.e.

Member nabla::operator+ (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m + m: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator+= (vector_expression< value_t, expr1, tag::storage > &left, const vector_expression< value_t, expr2, tag2 > &right)

v += v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator+= (vector_expression< value_t, expr1, tag::reference > &left, const vector_expression< value_t, expr2, tag2 > &right)

v += v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator+= (vector_expression< value_t, expr1, tag::storage > &left, const vector_expression< value_t, expr2, tag2 > &right)

v += v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator+= (vector_expression< value_t, expr1, tag::reference > &left, const vector_expression< value_t, expr2, tag2 > &right)

v += v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator+= (matrix_expression< value_t, expr1, tag::storage > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m += m: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator+= (matrix_expression< value_t, expr1, tag::storage > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m += m: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator- (const vector_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2 > &right)

v - v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator- (const matrix_expression< value_t, expr_t, tag > &a)

-m: algorithmic complexity of this operation is constant (i.e.

Member nabla::operator- (const vector_expression< value_t, expr1, tag1 > &left, const vector_expression< value_t, expr2, tag2 > &right)

v - v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator- (const matrix_expression< value_t, expr_t, tag > &a)

-m: algorithmic complexity of this operation is constant (i.e.

Member nabla::operator- (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m - m: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator- (const matrix_expression< value_t, expr1, tag1 > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m - m: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator- (const vector_expression< value_t, expr_t, tag > &a)

-v: algorithmic complexity of this operation is constant (i.e.

Member nabla::operator- (const vector_expression< value_t, expr_t, tag > &a)

-v: algorithmic complexity of this operation is constant (i.e.

Member nabla::operator-= (vector_expression< value_t, expr1, tag::storage > &left, const vector_expression< value_t, expr2, tag2 > &right)

v -= v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator-= (vector_expression< value_t, expr1, tag::reference > &left, const vector_expression< value_t, expr2, tag2 > &right)

v -= v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator-= (vector_expression< value_t, expr1, tag::storage > &left, const vector_expression< value_t, expr2, tag2 > &right)

v -= v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator-= (matrix_expression< value_t, expr1, tag::storage > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m -= m: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::operator-= (vector_expression< value_t, expr1, tag::reference > &left, const vector_expression< value_t, expr2, tag2 > &right)

v -= v: algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::operator-= (matrix_expression< value_t, expr1, tag::storage > &left, const matrix_expression< value_t, expr2, tag2 > &right)

m -= m: algorithmic complexity of this operation is square (i.e. O(n²)).

Member nabla::reshape (const matrix_expression< value_t, expr_t, tag > &a)

reshape<shape_id>(m): algorithmic complexity of this operation is constant (i.e. O(1)).

Member nabla::reshape (const matrix_expression< value_t, expr_t, tag > &a)

reshape<shape_id>(m): algorithmic complexity of this operation is constant (i.e. O(1)).

Member nabla::sqrnorm (const vector_expression< value_t, expr_t, tag > &v)

sqrnorm(v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::sqrnorm (const vector_expression< value_t, expr_t, tag > &v)

sqrnorm(v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::sum_of_products (const vector_expression< value_t, expr1, tag1 > &a, const vector_expression< value_t, expr2, tag2 > &b)

sum_of_products(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::sum_of_products (const vector_expression< value_t, expr1, tag1 > &a, const vector_expression< value_t, expr2, tag2 > &b)

sum_of_products(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::swap (vector_expression< value_t, expr1, tag::storage > &a, vector_expression< value_t, expr2, tag::storage > &b)

swap(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::swap (vector_expression< value_t, expr1, tag::storage > &a, vector_expression< value_t, expr2, tag::storage > &b)

swap(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::swap (vector_expression< value_t, expr1, tag::storage > &a, vector_ref< expr2, tag::reference, orientation > b)

swap(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::swap (vector_expression< value_t, expr1, tag::storage > &a, vector_ref< expr2, tag::reference, orientation > b)

swap(v, v): algorithmic complexity of this operation is linear (i.e. O(n)).

Member nabla::transpose (const matrix_expression< value_t, expr_t, tag > &a)

transpose(m): algorithmic complexity of this operation is constant (i.e.

Member nabla::transpose (const matrix_expression< value_t, expr_t, tag > &a)

transpose(m): algorithmic complexity of this operation is constant (i.e.