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.
Docker
To avoid the hassle of installing dependencies, you can use the provided Dockerfile
.
For example,
wget -q https://raw.githubusercontent.com/TLCFEM/vpmr/master/Dockerfile
docker build -t vpmr -f Dockerfile .
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 <float> precision multiplier (default, minimum: 1.5)
-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
The minimum required precision can be estimated by the parameter $$n$$. The algorithm involves the computation of $$C^{4n}{2n}$$ and $$2^{4n}$$. The number of precision bits shall be at least $$\log_2(C^{4n}{2n})+4n$$. In the implementation, this number will be further multiplied by the parameter $$m$$.
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-240515-pp310-pypy310_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a87f2e47aa970daf36249d8ce7e4a7b9096792a72179d2c1bb5562b7cbaabe54 |
|
MD5 | dd638f1fc4ac8118b3a9c7c02f34ede0 |
|
BLAKE2b-256 | 870c3f4bedd8aeb14045cb01b045498699fc35892ea316e766f562c613c09cb2 |
Hashes for pyvpmr-240515-pp310-pypy310_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ecca1e576355e96322be492e5b432f4d71e1bf305fce99af998d2c58b20e6a6b |
|
MD5 | 109361fe1f3e96720516498411163858 |
|
BLAKE2b-256 | c1599502d9aa6527ab5dbe9360e329dab2313a1d86a03228874d8e5d5e8bd32e |
Hashes for pyvpmr-240515-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 642ca5f2aec9fc2d5114417f769da2a9cfd58c2a29d452e97f1e93503b6ed72c |
|
MD5 | 1c12b3b76dbf7359c934fffc6132eac0 |
|
BLAKE2b-256 | 6430dcadc0eb6006283c4c33ea518bfbfd427334c8b5d124aff732be71969884 |
Hashes for pyvpmr-240515-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d0697b7a3a208678d840cf8d1a7a01a4037e67784b0098fae4da42e4be3c210a |
|
MD5 | 6a267e41f4b8937a57376611fa0cf2ec |
|
BLAKE2b-256 | 67a381fc6584ec74bddda6b1d65abb455daaab14baee76af7ab997e683932bbd |
Hashes for pyvpmr-240515-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 06ee3dcdea946a28da5e9df53178dd3bf5a7a4bf8ffa2641c9f187e0eed0512d |
|
MD5 | 4edad969312812f6dd345db251fa96e4 |
|
BLAKE2b-256 | 7127d26265bfe80abf3d6da85cedff68355064fcc761be1d56a51b8daefaf2a7 |
Hashes for pyvpmr-240515-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1c0e98940f59ceeb33fd9c175dc2454fb01bfe791290b4e3c206409c6db0398a |
|
MD5 | 86bef4a39ec59b579c83df81a1cd9e6c |
|
BLAKE2b-256 | 3b97c2569d138eb0a6c0753d000422d196f00fca23a010ef006931a5347c22b3 |
Hashes for pyvpmr-240515-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 18f5336d783224203ce9399b32e781f8f35bed2201939b27bd2db80da0722aaa |
|
MD5 | 34efd73b46c1ac810cf30b6561bcc178 |
|
BLAKE2b-256 | fb81492785d976424931ba8a844b70da57660603ae9081790fe7ac15a563c3eb |
Hashes for pyvpmr-240515-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 613d4dd0afd6b3e964ee58f2080171648ea309fc28c2933c9a7c998511ede8cc |
|
MD5 | 241e26377848d657c73fd6cf2999e7cb |
|
BLAKE2b-256 | f0012bbaec9c4701427bad1f21e72dfaa58105aba805273c3a34a6498f858001 |
Hashes for pyvpmr-240515-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c9f9affe4cd69ebcb72f0c8e666911908ef2224784defe9fba152dface5b3d66 |
|
MD5 | b4224ee663b2e468c858ef4f978312f8 |
|
BLAKE2b-256 | 8497fae311e099c77efa26da71c731b187ff91d9714f6b3123f5c7775239eed3 |
Hashes for pyvpmr-240515-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c339edbf91c1f6c6e78449f77c01735488e7389a452c3b4755d81efae0688bde |
|
MD5 | 8bf886d01bd8368c2b9dc04d201d3d28 |
|
BLAKE2b-256 | 6c41ac3f0db823fe403e9a503e3e7858fdf133357694c2654f3ebe86b8367d4e |
Hashes for pyvpmr-240515-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b7f3a213b55712cd528faa4db73da046ff5c8345549e4ca8043b7694a8343c7f |
|
MD5 | 862bd36017a7619cb5c3d57f7ac246f9 |
|
BLAKE2b-256 | 7b7fc5ef47a4724e8dc30f54c5fcd673c9ef4a28180640472a1ce7904650f9a8 |
Hashes for pyvpmr-240515-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9d6d3be440ff95bdcae8a70a55d49af2f206edafde3a83a9584296e326da82e7 |
|
MD5 | f23c0a1645da327bb6623c1986ec7bbc |
|
BLAKE2b-256 | 26073e894253745971c9df546f1fc164e4c0eb1e69bf1117118430203ad7b292 |
Hashes for pyvpmr-240515-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ebf61c5f05a11565b0322fbd5e94966212080714b8c8e6b1d169c11482249471 |
|
MD5 | 97933687b39bbc79325983bed0aedd14 |
|
BLAKE2b-256 | d99025346dc40c2f24450bd62ee3e2cda1dad5df53b4775c678b72c7686b1cd5 |
Hashes for pyvpmr-240515-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae1ff006ec430252db18798344188357e4926ffb9a8107e2ba54219a51dc6462 |
|
MD5 | 2a3de0f7017c7cbcef28b73befb6394f |
|
BLAKE2b-256 | 3226d37b3963f9094f485f3e1c7a6c9fd18ed24b5b310f080990a88ed08d0280 |
Hashes for pyvpmr-240515-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ec3dbb231291cddf6ce231df3d110d8b1634a50b482af2d36bfe1540be6b281a |
|
MD5 | 06e15db3fb3b4e1ed6e8a35f41a50477 |
|
BLAKE2b-256 | 3a0137a6999a01b934e058c3716067bec6f58d29a9e0d3e7a267da15e596f299 |
Hashes for pyvpmr-240515-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3cbd6de410fac1f34d029418e04a62136333f0db15a08ab42d4dc397481c739f |
|
MD5 | 3849ea5a4ed5ff5597c802e19442f3a4 |
|
BLAKE2b-256 | e7fa9376f05179ea6826b11d9777104dea9175922fce1da494bd417ee5358454 |
Hashes for pyvpmr-240515-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 225b0b90e5c286afcb892350595dad8a62771f92172b63a43d486b3e46f49e68 |
|
MD5 | e599b8821c0042e7d8414be68d0a970a |
|
BLAKE2b-256 | 67cf7f0ef03df5605cce63e3762a55e2b1fd28295a22ba957d78ec382835dd52 |
Hashes for pyvpmr-240515-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6f96d90620fa205a4ab48c07493789177ffcbc28660b4318aecb10a726c45d3d |
|
MD5 | b26b458f00e8ff8ec3106c4912cc33e4 |
|
BLAKE2b-256 | a6e05957659fdd6f064a6197d763117f73dbab53025046367a4d9e7f5b2d0426 |
Hashes for pyvpmr-240515-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 26c91714a98d05d07563ac395fcaa1a41ef253603367254c16185252255bfc77 |
|
MD5 | 9bfc386745c0a0ef2d8745470ca63445 |
|
BLAKE2b-256 | effc1bfb132c91ada4e21bd8f171c2ca7513cebe2f16a88462f725ac527c561b |
Hashes for pyvpmr-240515-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7ac52ab810c9c8dc785788f7f5e1fed9eb37c7dad34839215b0d407e0d77ddcd |
|
MD5 | 9924485c74f4b42ef77ea98e41afe5ff |
|
BLAKE2b-256 | e9d388331140eb902bb5c912fa47bb3a4ea618ecd54029b036ecc3219904eec0 |