SYNAPS (SYmbolic Numeric ApplicationS) » Linear Algebra

Structured matrices

Structured matrices are parameterised by the internal representation:

template<class R> struct MatrStr<R>;

Structured matrices are two-dimensional arrays which can be represented by $\mathcal{O}(n)$ values, where $n$ is the size of the matrix. This class provides classical arithmetic operations such as addition, substraction, multiplication by scalars, vectors, matrices . . . The product of two structured matrices is usually not a structured matrices (at least of the same type) and therefore is not implemented. The product of a structured matrices by a vector can usually be performed in almost linear time, ie. in $\mathcal{O}(n \log (n))$ (or $\mathcal{O}(n \log (n) \log^2 (n)$ according to the field), using FFT.

Examples of containers

Toeplitz container

A matrix $T = (t_{i, j})_{1 \leqslant i, j \leqslant n}$ is a Toeplitz matrix if for all $i, j$, the entry $t_{i, j}$ depends only on $i - j$, that is if $t_{i, j} = t_{i + 1, j + 1}$ for all pairs of $(i, j)$ and $(i + 1, j + 1)$ for which the entries $t_{i, j}$ and $t_{i + 1, j + 1}$ are defined. Associated with a Toeplitz matrix, we have the Toeplitz operator which is a projection composed with the multiplication operator by a univariate polynomial in $K [x]$ (see [BP94]). An interesting point of this definition is that the product of a $n \times n$ Toeplitz matrix by a vector is a subvector of the coefficient vector of the product of two polynomials of K[x]. This product can be done within $\mathcal{O}(n \log (n))$ (or $\mathcal{O}(n \log (n) \log^2 (n)$ according to the field) operations using FFT.

An implementation of such data-structure is available as

template<class C> linalg::toeplitz<C>;

See also:
synaps/linalg/toeplitz.h

Hankel container

A matrix $H = (h_{i, j})$ is a Hankel matrix if its entries $h_{i, j}$ depends only on $i + j$, that is, if $h_{i + 1, j + 1} = h_{i, j}$ for all pairs $(i, j)$ for which the entries are defined. To this kind of matrix, we can associate a Hankel operator which is defined as the projection of the multiplication by a fixed Laurent polynomial (a Laurent polynomial is a polynomial of $K [x, x^{- 1}]$, that is a polynomial in both the variables $x$ and $x^{- 1}$). So we can compute the product of a $n \times n$ Hankel matrix by a vector as a subvector of the product of a fixed polynomial $h (x)$ by a polynomial in $x^{- 1}$. This can also be done within $O (n \log (n))$ ops (or $O (n \log (n) \log^2 (n))$ according to the field), using FFT. See [4].

An implementation of such data-structure is available as

template<class C> linalg::hankel<C>;

See also:
synaps/linalg/hankel.h

Example

#include <synaps/linalg/MatrStr.H>
#include <synaps/linalg/hankel.H>
typedef MatrStr<linalg::hankel<double> > mstr_t;

int main(int argc, char** argv) 
{
  double v[]={1,2,1,1,3,4,2,2,5,5,5,5,-2, 1,2,3,1, -2.8,-2.4,1,.2,5.8};
  mstr_t A(4,4,v);
  std::cout << A << std::endl;

\[ A \assign \left(\begin{array}{cccc} 1 & 2 & 1 & 1\\ 2 & 1 & 1 & 3\\ 1 & 1 & 3 & 4\\ 1 & 3 & 4 & 5 \end{array}\right) \] 

}

Implementation

See also:
synaps/linalg/MatrStr.h

SYNAPS DOCUMENTATION
logo