## `linalg::vandermondeSolve` -- solve a linear Vandermonde system

#### Introduction

`linalg::vandermondeSolve``(v, y)` returns the solution x of the linear Vandermonde system sum(v[i]^(j-1)*x[j], j=1..n) = y[i] for i=1..n.

#### Call(s)

`linalg::vandermondeSolve(v, y)`
`linalg::vandermondeSolve(v, y, Transposed)`

#### Parameters

`v` | - | a vector with distinct elements (a vector is an n x 1 or 1 x n matrix of category `Cat::Matrix`)
`y` | - | a vector of the same dimension and domain type as `v`

#### Options

`Transposed` | - | returns the solution x of the transposed system sum(v[j]^(i-1)*x[j], j=1..n) = y[i] for i=1..n.

#### Returns

a vector of the same domain type as `y`.

#### Related Functions

`solve`, `linsolve`, `linalg::matlinsolve`, `numeric::lagrange`, `numeric::linsolve`, `numeric::matlinsolve`

#### Details

- `linalg::vandermondeSolve` uses O(n^2) elementary operations to solve the Vandermonde system. It is faster than the general system solver `solve` and the solver `linsolve`, `numeric::linsolve`, `linalg::matlinsolve` and `numeric::matlinsolve` for linear systems.
- The solution x=[x1,..,xn] returned by

  > `linalg::vandermondeSolve``([vi $i=1..n], [yi $i=1..n])`

  yields the coefficients of the polynomial p(v)=x1+x2*v+..+xn*v^n-1 interpolating the data table (v1,y1), ..., (vn,yn), i.e.,

      p(v0)=y0,..,p(vn)=yn .

  See example 1.

#### Example 1

The Vandermonde points v and the right hand side y of the linear system are entered as vectors:

    >> delete y0, y1, y2:
       v := matrix([[0, 1, 2]]); y:= matrix([[y0, y1, y2]])

                                    +-       -+
                                    | 0, 1, 2 |
                                    +-       -+

                                  +-          -+
                                  | y0, y1, y2 |
                                  +-          -+

The solution vector is:

    >> x := linalg::vandermondeSolve(v, y)

                    +-                                      -+
                    |        3 y0          y2  y0        y2  |
                    |  y0, - ---- + 2 y1 - --, -- - y1 + --  |
                    |         2            2   2         2   |
                    +-                                      -+

The solution yields the coefficients of the interpolating polynomial:

    >> P := v -> _plus(x[i+1]*v^i $ i=0..2):

through the points (0,y0), (1,y1), (2,y2):

    >> P(v[1]), P(v[2]), P(v[3])

                                    y0, y1, y2

With the optional argument Transposed, the linear system with the transposed Vandermonde matrix corresponding to `v` is solved:

    >> linalg::vandermondeSolve(v, y, Transposed)

                    +-                                      -+
                    |       3 y1   y2               y1   y2  |
                    |  y0 - ---- + --, 2 y1 - y2, - -- + --  |
                    |        2     2                2    2   |
                    +-                                      -+

#### Example 2

The Vandermonde points v and the right hand side y of the linear system are entered as 2 x 1 matrices:

    >> Mat := Dom::Matrix(Dom::ExpressionField(normal)):

    >> delete v1, v2, y1, y2:
       v := Mat([v1, v2]): y:= Mat([y1, y2]):

We define the vectors over the domain `Dom::ExpressionField(normal)` in order to simplify intermediate computations.

Next, we compute the solution of the corresponding Vandermonde system:

    >> x := linalg::vandermondeSolve(v, y)

                               +-                 -+
                               |  - v1 y2 + v2 y1  |
                               |  ---------------  |
                               |     - v1 + v2     |
                               |                   |
                               |     - y1 + y2     |
                               |     ---------     |
                               |     - v1 + v2     |
                               +-                 -+

We construct the Vandermonde matrix `V` and verify the result:

    >> V := Mat([[1, v[1]], [1, v[2]]])

                                    +-       -+
                                    |  1, v1  |
                                    |         |
                                    |  1, v2  |
                                    +-       -+

    >> V * x

                                     +-    -+
                                     |  y1  |
                                     |      |
                                     |  y2  |
                                     +-    -+

#### Example 3

We solve a Vandermonde system over the field Z7 (the integers modulo 7) represented by the domain `Dom::IntegerMod(7)`:

    >> MatZ7 := Dom::Matrix(Dom::IntegerMod(7)):
       v := MatZ7([1, 2, 3]): y := MatZ7([0, 1, 2]):

    >> linalg::vandermondeSolve(v, y)

                                   +-         -+
                                   |  6 mod 7  |
                                   |           |
                                   |  1 mod 7  |
                                   |           |
                                   |  0 mod 7  |
                                   +-         -+

#### Background

- The Vandermonde matrix

                 ( 1  v[1] v[1]^2 .. v[1]^(n-1) )
                 ( 1  v[2] v[2]^2 .. v[2]^(n-1) )
             V = ( ..  ..   ..    ..  ..        )
                 ( 1  v[n] v[n]^2 .. v[n]^(n-1) )

  generated by v=[v[1],..,v[n]] is invertible if and only if the v[i] are distinct.
- The vector x returned by `linalg::vandermondeSolve``(x, y)` solves V*x=y and is unique.
- The vector x returned by `linalg::vandermondeSolve``(x, y, Transposed)` solves transpose(V)*x=y and is unique.

#### Changes

- new function

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000