Fastest Analytic-Form Inverse of Square Vandermonde Matrices
Fast Analytical-Form Inverse of Vandermonde Matrix
Introduction
invvander
inverses an m-by-n Vandermonde matrix:
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
- 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
Compatibilidad con las plataformas
Windows macOS LinuxEtiquetas
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Descubra Live Editor
Cree scripts con código, salida y texto formateado en un documento ejecutable.
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;
|
||
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 |