Fastest Analytic-Form Inverse of Square Vandermonde Matrices

Versión 1.1.23 (15.9 KB) por Yu Chen
Compute the analytic-form inverse of a square Vandermonde matrix in 5.5n^2 flops; Support the pseudoinverse of a Vandermonde matrix.
17 descargas
Actualizado 30 May 2023

Fast Analytical-Form Inverse of Vandermonde Matrix

Introduction

invvander inverses an m-by-n Vandermonde matrix:

vanderm

Its syntax is similar to the Octave/MATLAB built-in function vander.

invvander computes the analytic-form inverse of any square Vandermonde matrix in 5.5n^2 floating point operations (flops). invvander introduces significantly less rounding errors because it avoids numerical matrix inversion (Vandemonde matrices are usually ill-conditioned). Moreover, invvander might be the fastest algorithm so far because is faster than Parker's algorithm that requires 6n^2 flops [1].

Given that [x1,x2,...x11] =1:0.5:6, running Example 3 below in Octave shows that invvander is 150.86 times more accurate and 40.93 times faster than inv.

Algorithms

The algorithm calculates the analytic-form inverse of a square Vandermonde matrix. It is implemented based on a draft as well as C codes I developed: https://github.com/yveschris/possibly-the-fastest-analytic-form-inverse-vandermonde-matrix

The algorithm of the calculating the pseudoinverse of a rectangular Vandermonde matrix is standard. It implemented based on the QR decomposition, followed by a forward and a back substitutions.

Syntax and Function Description

B = invvander(v) returns the inverse of a square Vandermonde Matrix, i.e., m = n for the above matrix V. v has to be a row vector and v = [x1, x2, ..., xn].

B = invvander(v, m) returns the pseudoinverse of an m-by-n rectangular Vandermonde Matrix. v has to be a row vector and v = [x1, x2, ..., xn] while m has to be a scalar and positive integer of the above matrix V. If m equals the number of v, then B is the inversed square Vandermonder matrix.

Examples

Example 1: inverse of an n-by-n square Vandermonde matrix:

v = 1:.5:6;
B = invvander(v);

Example 2: pseudoinverse of an m-by-n rectangular Vandermonde matrix:

v = 1:.5:6;
B = invvander(v, 20);

Example 3: Error reduction and runtime improvement testing when dealing with a square Vandermonde matrix:

v = 1:.5:6;
A = vanderm(v);

e1 = norm(A - inv(inv(A)), 2);
e2 = norm(A - inv(invvander(v)), 2);
disp(['e1/e2 = ' num2str(e1 / e2)]);
% Octave Output: e1/e2 = 150.8606

tic
invvander(v);
t1 = toc
tic
inv(A);
t2 = toc
disp(['t1/t2 = ' num2str(t1 / t2)]);
% Octave Output: t1/t2 = 40.9325

References

  1. F. Parker, Inverses of Vandermonde matrices, Amer. Math. Monthly 71,410-411, (1964).

Citar como

Yu Chen (2024). Fastest Analytic-Form Inverse of Square Vandermonde Matrices (https://github.com/yveschris/high-precision-inverse-of-vandermonde-matrix/releases/tag/1.1.23), GitHub. Recuperado .

Compatibilidad con la versión de MATLAB
Se creó con R2021a
Compatible con cualquier versión
Compatibilidad con las plataformas
Windows macOS Linux
Etiquetas Añadir etiquetas

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

No se pueden descargar versiones que utilicen la rama predeterminada de GitHub

Versión Publicado Notas de la versión
1.1.23

See release notes for this release on GitHub: https://github.com/yveschris/high-precision-inverse-of-vandermonde-matrix/releases/tag/1.1.23

1.1.22

connect with github

1.1.21

updated figure.

1.1.20

figure size updated.

1.1.18

A comparison figure added.

1.1.17

updated the title.

1.1.16

updated description.

1.1.15

summary corected.

1.1.14

corrected the summary.

1.1.13

performance enhancement.

1.1.12

Highlight the high-performance benefits of the algorithm.

1.1.11

bug fixed. Included a vanderm.m and example.m

description updated.

1.1.10

improve the readability of m file.

1.1.9

forgot to upload the zip file.

1.1.8

Bug fixed when V is under-determined. Description has been updated as well.

1.1.7

optimze the flow in the m function.

1.1.6

fix a bug in the m file. updated the example 3 in descrip.

1.1.5

fix a bug in the m function.

1.1.4

updated descr.

1.1.3

Updated description.

1.1.2

updated description.

1.1.1

updated description.

1.1.0

1) Updated description;
2) Able to solve non-square Vandermonde matrices.

1.0.3

Some typos are corrected.

1.0.2

update the function name to invvander, which is consistent with the naming convention in Matlab, e.g., invhilb. I also added an input argument check.

1.0.1

Description updated.

1.0.0

Para consultar o notificar algún problema sobre este complemento de GitHub, visite el repositorio de GitHub.
Para consultar o notificar algún problema sobre este complemento de GitHub, visite el repositorio de GitHub.