The VPMR Algorithm
Project description
VPMR C++ Implementation
Call For Help
- more performant parallel SVD algorithm:
eigen
only provides sequential SVD - alternative integration: currently only Gauss-Legendre quadrature is available
What Is This?
This is a C++ implementation of the VPMR algorithm to compute the approximation of arbitrary smooth kernel. A Python package is also provided.
Check the reference paper 10.1007/s10915-022-01999-1 and the original MATLAB implementation for more details.
In short, the algorithm tries to find a summation of exponentials to approximate a given kernel function. In mathematical terms, it looks for a set of $m_j$ and $s_j$ such that
\max_{t\in{}I}\left\|g(t)-\sum_jm_j\exp(-s_jt)\right\|<\epsilon.
In the above, $g(t)$ is the given kernel function and $\epsilon$ is the prescribed tolerance.
Dependency
The following libraries are required:
- gmp for multiple precision arithmetic
- mpfr for multiple-precision floating-point computations
- tbb for parallel computing
The following libraries are included:
- mpreal
mpreal
type C++ wrapper, included - BigInt
BigInt
arbitrary large integer for combinatorial number, included - Eigen for matrix decomposition, included
- exprtk for expression parsing, included
- exprtk-custom-types for
mpreal
support, included
How To
Python Package
[!WARNING] The Python module needs external libraries to be installed.
[!WARNING] Windows users need to have a working MSYS2 environment. See below for more details. For other environments, you need to figure out how to install
gmp
andmpfr
on your own.
On RPM-based Linux distributions (using dnf
), if you are:
- compiling the application from source (or wheels are not
available),
sudo dnf install -y gcc-c++ tbb-devel mpfr-devel gmp-devel
- using the packaged binary (wheels are available),
sudo dnf install -y gmp mpfr tbb
On DEB-based Linux distributions (using apt
), you need to sudo apt install -y libtbb-dev libmpfr-dev libgmp-dev
.
On macOS, you need to brew install tbb mpfr gmp
.
Then install the package with pip
.
pip install pyvpmr
If the corresponding wheel is not available, the package will be compiled, which takes a few minutes.
The execution of the algorithm always requires available gmp
, mpfr
and tbb
libraries.
Jumpstart
import numpy as np
from pyvpmr import vpmr, plot
def kernel(x):
return np.exp(-x ** 2 / 4)
if __name__ == '__main__':
m, s = vpmr(n=50, k='exp(-t^2/4)')
plot(m, s, kernel)
Compile Binary
[!WARNING] The application relies on
eigen
andexprtk
, which depend on very heavy usage of templates. The compilation would take minutes and around 2 GB memory. You need to install librariesgmp
,mpfr
andtbb
before compiling.
Windows
Use the following instructions based on MSYS2, or follow the Linux instructions below with WSL.
# install necessary packages
pacman -S git mingw-w64-x86_64-cmake mingw-w64-x86_64-tbb mingw-w64-x86_64-gcc mingw-w64-x86_64-ninja mingw-w64-x86_64-gmp mingw-w64-x86_64-mpfr
# clone the repository
git clone --depth 1 https://github.com/TLCFEM/vpmr.git
# initialise submodules
cd vpmr
git submodule update --init --recursive
# apply patch to enable parallel evaluation of some loops in SVD
cd eigen && git apply --ignore-space-change --ignore-whitespace ../patch_size.patch && cd ..
# configure and compile
cmake -G Ninja -DCMAKE_BUILD_TYPE=Release .
ninja
Linux
The following is based on Fedora.
sudo dnf install gcc g++ gfortran cmake git -y
sudo dnf install tbb-devel mpfr-devel gmp-devel -y
git clone --depth 1 https://github.com/TLCFEM/vpmr.git
cd vpmr
git submodule update --init --recursive
cd eigen && git apply --ignore-space-change --ignore-whitespace ../patch_size.patch && cd ..
cmake -DCMAKE_BUILD_TYPE=Release .
make
Usage
All available options are:
Usage: vpmr [options]
Options:
-n <int> number of terms (default: 10)
-d <int> number of precision bits (default: 512)
-q <int> quadrature order (default: 500)
-m <int> precision multiplier (default: 6)
-nc <int> controls the maximum exponent (default: 4)
-e <float> tolerance (default: 1E-8)
-k <string> file name of kernel function (default: exp(-t^2/4))
-s print singular values
-w print weights
-h print this help message
Example
The default kernel is exp(-t^2/4)
. One can run the application with the following command:
./vpmr -n 30
The output is:
Using the following parameters:
nc = 4.
n = 30.
order = 500.
precision = 336.
tolerance = 1.0000e-08.
kernel = exp(-t*t/4).
[1/6] Computing weights... [60/60]
[2/6] Solving Lyapunov equation...
[3/6] Solving SVD...
[4/6] Transforming (P=+9)...
[5/6] Solving eigen decomposition...
[6/6] Done.
M =
+1.1745193571738943e+01-1.4261645574068720e-100j
-5.5143304351134397e+00+5.7204056791636839e+00j
-5.5143304351134397e+00-5.7204056791636839e+00j
-1.6161617424833762e-02+2.3459542440459513e+00j
-1.6161617424833762e-02-2.3459542440459513e+00j
+1.6338578576177487e-01+1.9308431539218418e-01j
+1.6338578576177487e-01-1.9308431539218418e-01j
-5.4905134221689715e-03+2.2104939243740062e-03j
-5.4905134221689715e-03-2.2104939243740062e-03j
S =
+1.8757961592204051e+00-0.0000000000000000e+00j
+1.8700580506914817e+00+6.2013413918954552e-01j
+1.8700580506914817e+00-6.2013413918954552e-01j
+1.8521958553280000e+00-1.2601975249082220e+00j
+1.8521958553280000e+00+1.2601975249082220e+00j
+1.8197653300065935e+00+1.9494562062795735e+00j
+1.8197653300065935e+00-1.9494562062795735e+00j
+1.7655956664692953e+00-2.7555720406099038e+00j
+1.7655956664692953e+00+2.7555720406099038e+00j
Running time: 3 s.
Arbitrary Kernel
For arbitrary kernel, it is necessary to provide the kernel function in a text file.
The file should contain the kernel expressed as a function of variable t
.
The exprtk
is used to parse the expression and compute the value.
The provided kernel function must be valid and supported by exprtk
.
For example, to compute the approximation of exp(-t^2/10)
, one can create a file kernel.txt
with the following
content:
exp(-t*t/10)
In the following, the kernel function is echoed to a file and then used as an input to the application.
echo "exp(-t*t/10)" > kernel.txt
./vpmr -n 60 -k kernel.txt -e 1e-12
Binary
The binary requires available gmp
, mpfr
and tbb
libraries.
❯ ldd vpmr
linux-vdso.so.1 (0x00007ffcf3121000)
libgmp.so.10 => /lib64/libgmp.so.10 (0x00007f72087e8000)
libmpfr.so.6 => /lib64/libmpfr.so.6 (0x00007f7208736000)
libtbb.so.2 => /lib64/libtbb.so.2 (0x00007f72086f2000)
libstdc++.so.6 => /lib64/libstdc++.so.6 (0x00007f7208400000)
libm.so.6 => /lib64/libm.so.6 (0x00007f7208320000)
libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x00007f72086d0000)
libc.so.6 => /lib64/libc.so.6 (0x00007f7208143000)
/lib64/ld-linux-x86-64.so.2 (0x00007f72088a1000)
The distributed appimage
is portable.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for pyvpmr-240307-pp310-pypy310_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ef3bd29d324511c84da8c5c5ca3ec2ebb15d4a95efee1f8934eabfeb6ddfa49a |
|
MD5 | f1c91c96510f42271cb4fefd6cc5feb9 |
|
BLAKE2b-256 | 0867e90463998d0c4234041425dec0bcd08d5b32c3a45fc37d8f36907f9f4df8 |
Hashes for pyvpmr-240307-pp310-pypy310_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ff2c71e537038c6120ab9056dc94fc5039dc97a1615dceaf38f733b8b0b5a723 |
|
MD5 | d46193bf77052bf3817efff661be60a2 |
|
BLAKE2b-256 | d4865423a29b992b76805066a2f6a22ea9bcfbb71594e8313932da2c59a5629b |
Hashes for pyvpmr-240307-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 005fff171c8bbb3f196aa1eab8f35d0a061eed3f8b8b7d2ed7f9823438072947 |
|
MD5 | 1ef45db44f55dc5c3918bf9d8e8f3ecc |
|
BLAKE2b-256 | 764d3f81400051fbb701eefe2e56295316cdd5bf769c49514d347c5c03ecfc83 |
Hashes for pyvpmr-240307-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b2a3718465f8bd83c7972cd1cd0f6295c64fa16bceafc8c10e61da54a301083d |
|
MD5 | c562f69d796f65380e408a5223859557 |
|
BLAKE2b-256 | b49b9a8a7575cab54d8b8efeaffddc34a556309e63e86d512124758b6272145a |
Hashes for pyvpmr-240307-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3a964def3a7eb09a9c7ed44a2ded93abd3bd4d4941286aab098d69d799f934bf |
|
MD5 | 97de7761d8ab8096e4ab53fbca25154f |
|
BLAKE2b-256 | 45c9656d6018044e392ecd9e384cbe511c1ea1049d59ce1f7f8968650df74195 |
Hashes for pyvpmr-240307-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c0d204f183ec0baee94b5798957005f83be6013d250c0b2e55220e8bfb4c89e7 |
|
MD5 | dcca2ef9c01d06958c2b1760e01ee87b |
|
BLAKE2b-256 | ec55262433068ff525aa760bbb9d3170ef11e79ea3d1d4b590976c00b9ef04b9 |
Hashes for pyvpmr-240307-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | be5f3b2ee8c58e5b9a5e79a579ad3b034bd08982554577503259f48eefea1b16 |
|
MD5 | 4fbdc917e54092239d210bf1608d7d1e |
|
BLAKE2b-256 | a1265aaef1d72f7014a952311cfc563ac131a05f0bea18884218260101dc130f |
Hashes for pyvpmr-240307-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 714c99ba0eca9cf740483d62a0f3670872730b17ec4d72d54e6fbd7501e7a336 |
|
MD5 | 3f95599b4aa619ab93a757f5866552d8 |
|
BLAKE2b-256 | d56f9c1a3c5618578ac11f939499d50b3727df2282dbfbe8eff40cdd43498402 |
Hashes for pyvpmr-240307-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dd89e0767775123277d9662838eb5a1b50bd721f70fa207095c2f9fed39eea79 |
|
MD5 | ecb51e74c88394f453b89b8dfac274c8 |
|
BLAKE2b-256 | f0e37e18a28678dda3d6f5284029bf2a244c09bf66d2808364d5f63093dfd97c |
Hashes for pyvpmr-240307-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 26b724644841fbe67968abc5fae9b7dbfecaeab59e18fc00173730231f4adebd |
|
MD5 | cf1ae79c608589d9129b7134bfa9a3d4 |
|
BLAKE2b-256 | 04c3d793305719665953de8d0f749f3008d4c160873e43e795a69482b74ccdcc |
Hashes for pyvpmr-240307-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 763a05faa8e3d7b6e133d16e0d62f7f5fd5380b86e879c948c979f90e036dfcd |
|
MD5 | 4a4cf41fc4543ba0eacf29e5c2fd9155 |
|
BLAKE2b-256 | cd9b733b77cd8547c77356817a9fceec58fb50bc809fc466f785c89ef4400d0e |
Hashes for pyvpmr-240307-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a1ae39fac3618c9810f8faa7dc0005db2489064d8afc7f023f7d84d99be53860 |
|
MD5 | f9c3d71337c771af8351c19b4b494484 |
|
BLAKE2b-256 | bd6ae13492f40208d88949a872d464af50bef7a47d56f2cc58e77d98c0e1cf65 |
Hashes for pyvpmr-240307-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 49fa651d81b63ddeaa206f076a5a38c89527010ebd545936301f904f9d6c64e4 |
|
MD5 | 11bd87fb20102590f7fa22ff4b06f431 |
|
BLAKE2b-256 | f88cdc866d44a5430c5d6758898588971380dbcbf827a775075fda4ab91ded52 |
Hashes for pyvpmr-240307-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e301faf4f8109cdb437925d2a0db71f787a482148c9301b75bbd50ae370c60e9 |
|
MD5 | e374d3b819c077c24b8b62cd7effd6c0 |
|
BLAKE2b-256 | 19054ac03ca3548ab8351e8ac7539c83d0bbe4b16b692e4d0284c8fefc8452bc |
Hashes for pyvpmr-240307-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 22969cc97ecf929b6249550a6c9a85eacdb92183396ac746a609db90588206d6 |
|
MD5 | 33a63d2ae181b8517865a8eb11341c36 |
|
BLAKE2b-256 | a528c068e36aa1a4d68e8dcd01a2ebe316ab1726894ae2db2d16a6118c29d307 |
Hashes for pyvpmr-240307-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bdb889a080c6f32d9725f5c5d7cb515d499d5ded55f37a3a47b317867351300a |
|
MD5 | e8233f159995ae19800892b93451080d |
|
BLAKE2b-256 | 6ad8e6a933145c679ab207709f39a9871d5fcb569b4add343f959bf3c209ac63 |
Hashes for pyvpmr-240307-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 40d09127239e8e80fdc10c2a4e59ea5c7bd48c90a75b14c1b5d1b4ccc0197424 |
|
MD5 | dc32a4b7ad9197e91eeaa65f084350cc |
|
BLAKE2b-256 | 747335bf54b3e39dfd1ac152c97818b83651ce21f8e57cd4afb0def878fd6496 |
Hashes for pyvpmr-240307-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 296fb83afde838bcaf80850b136148446df1f4f2336641753a2b0c7e817b56fa |
|
MD5 | 37c9e367022cbab8b9a7ce62f511a6ef |
|
BLAKE2b-256 | 0f636b567dcdd0ea772de5b5064c37dcd0a18229db6834db52a537e3316d0b15 |
Hashes for pyvpmr-240307-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 90381664e690b8e1f2088ef08618408f8e0e1844e941197447a5bdbb49b90e99 |
|
MD5 | a40afd03c2370a1b6aaed171a9283c11 |
|
BLAKE2b-256 | e47f1750bd8aeb0fb82814ae4e20e98e0fdd0ce03d15c25829628ac51be2fab2 |
Hashes for pyvpmr-240307-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c09d41f7d419865df7e49529828b2c7738e7ea9f96dab1c5b785c01b70248beb |
|
MD5 | 9907d78d58d5c85e7ad5de73d4fd4992 |
|
BLAKE2b-256 | 9e67f9b57e0bfb1291fed1c33a93888ad2d13184f69c4bb8e8f457be147f754a |