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-240308-pp310-pypy310_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5f1a20c8cd81ebc158adc32f80fcfa73f2c8905c87a3cf0c530f8753bb683ef0 |
|
MD5 | cd67895a9d90231928304481b53d3bf0 |
|
BLAKE2b-256 | adef03b79b06bfb002c252891c3fe45374c9770a1b466d0d202c7db95c23c31a |
Hashes for pyvpmr-240308-pp310-pypy310_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3305d2b31dc66ab0ecf42a7fb1531f5029b8cf61f1b1d5ecd32c819c7aae9c87 |
|
MD5 | eccac2d929327e197b38431637e4c141 |
|
BLAKE2b-256 | 8eeab76dfedc5fc766709cfb2f8793895a5da9d36dcaddb050eae2ff6dae7c9d |
Hashes for pyvpmr-240308-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5da08668b4b20d92500dca976f007bd498913157708960b2ead2464177b23aca |
|
MD5 | 2314f442daa6efa69ae97acadc9213f6 |
|
BLAKE2b-256 | b3568950345a20637512ee0b106bed2768ce167e53857a7a16e225fbfeee39a6 |
Hashes for pyvpmr-240308-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 49d3587844f14d5a48ffd0e7a4fad22e71f425f64c38da5e7ad012df4c545dea |
|
MD5 | fa7055b297bcbef67e1a16d2d7c705b6 |
|
BLAKE2b-256 | ad78e869018baa411ec9100e3bcd410eda677daec235e75a61404fb22efb48de |
Hashes for pyvpmr-240308-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dfde2114efb2a178db94a1b2ec6447008417018960663ad7660e17ff8d7034c0 |
|
MD5 | 33a1f1b70c34e4e6dc38ee4d02dfe844 |
|
BLAKE2b-256 | 3eff3551a4b1be2eb5da4c04ce38d9c038416ee1b21c75f18a03c024bab4ae81 |
Hashes for pyvpmr-240308-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ecf7b81d8a5d6eb5ccb8eebe90698c05522ee473c8acf3e825c52de893700acf |
|
MD5 | 7db5517548d52aac0f18d89ded50e85c |
|
BLAKE2b-256 | 8517adbfb2444db2563345e1500e038acca87212e315906963ec6a6b5574a512 |
Hashes for pyvpmr-240308-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2e985454ff147fd12a171e7ce2e10420370614615aa00bacf12ddf7975474592 |
|
MD5 | ae7270689fa30a128c1c9255bfa5e5aa |
|
BLAKE2b-256 | 86e9137eec7e4bda57beb9b0940a5f5999c4a2105a151f9890230093ec0dcb20 |
Hashes for pyvpmr-240308-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1793fdf2457d6b2d5db29dd94eebe940c9d075596eb3735e72e314542c888fc1 |
|
MD5 | faffdd63c8731d383c85bcd6d0851505 |
|
BLAKE2b-256 | 786762f4881fb1459da114ed04cbf13d4cfb33615fb5596e678870c0c079a726 |
Hashes for pyvpmr-240308-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4e6bc921c32e87f0935d1a6a80e27fb9318869bca29e9e99d563e71a026ffa13 |
|
MD5 | ea981c7c392e2b25072f65bab97a6d7f |
|
BLAKE2b-256 | b89ab1fa65506163599c219b088ce604709f35b3a62813c86bac4b948583cb3d |
Hashes for pyvpmr-240308-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f9938ca28fe4f71ebd33fe77f951b05b5ea690e263b13a7d62af0bf9cfde8129 |
|
MD5 | 4082ec2dadaca9f8dae3ed57e9267973 |
|
BLAKE2b-256 | e558205b3a66c970f959ea1dbdd45981ccf2a9f1c9e4baf52f1203ba4d929f28 |
Hashes for pyvpmr-240308-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 37bcbbc121c47eda9f141c508154f83d68bd504fcdc1de15406377dad1c96db7 |
|
MD5 | a383edaae40edbca64619098c92c58e5 |
|
BLAKE2b-256 | 7a1037a62648a1c68d297bc75f6931332fe66260839aee920a0cfd8a78e27c36 |
Hashes for pyvpmr-240308-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4a6dbf9b7e548a9bc32f09befba1a6ff7900b4c0559dc08139c5486a48d69435 |
|
MD5 | c3248d04f3c6458f3295423a4d687d61 |
|
BLAKE2b-256 | f1f9cea3d1f39171d36a386f0b9f03f1b0c142092a7ba2a6e0c577121608478a |
Hashes for pyvpmr-240308-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5e30885afd9d27513681b83a13fcb215eeb04cb49c7461c247aadff8548f87c7 |
|
MD5 | b00079c98fa8872648bff82004dd27e0 |
|
BLAKE2b-256 | 9cf825f0d672542ace63f7ee5d504897ad6672b92fd6132455a4d49aadfadd51 |
Hashes for pyvpmr-240308-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4f073792946f48c41b625092efbdf2d51debe42e865f3e16bd7d6bdfa97168bc |
|
MD5 | fdf695f294a12a78ebbeb98659e3b5db |
|
BLAKE2b-256 | a57a89c3d4a5c22f337b262ff94747a7dce45efe889d33bdc2129f811e34d68f |
Hashes for pyvpmr-240308-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9050e3596301b38edb655eeaa30e39f52c865614d6ee9423d1d2c34df827538b |
|
MD5 | 740316ae5547885ac9da741917097917 |
|
BLAKE2b-256 | 7a6fa5a0d827b771c294198cac6c81bcb7389ad8d86addaffe3cc03a1f303573 |
Hashes for pyvpmr-240308-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bae3e04f501959f25aca3e6f4f64f72830f5bf80180a5ef08b2295e2e8208be9 |
|
MD5 | 64d7645b624157d09d24d15ab10551b8 |
|
BLAKE2b-256 | bbfe6d425a351c210dddf32f270f0bb3e01fe8fa3b356b4b42b20260cf627f75 |
Hashes for pyvpmr-240308-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8a1466907d564ef19569602d3b3855d9566a85d54d26f63063f86b0d7fb0442d |
|
MD5 | 3d32ab57330fe9f3e675a4af68fcf49b |
|
BLAKE2b-256 | 5ba48d87f9510613e5c4b2f3c7f8af36e549ecc4e6cc55469d43504a4195d836 |
Hashes for pyvpmr-240308-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9efbf9ad57a5ab2d4ca930abe7425bc76933fd47a4ecc5eb9a522afb8fd99dd9 |
|
MD5 | 56842bbc4bcd9af440b926d3c74084b9 |
|
BLAKE2b-256 | 85385d67385f0776548e1c51138e3740b933e24396312e9cd66307fa80fb841f |
Hashes for pyvpmr-240308-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8f4f360011994853e96729d1aed7ef6f5fa6d3edebd1f0cd1590432d849a598a |
|
MD5 | e6d890fe1ee3b6651c9015386908fa0c |
|
BLAKE2b-256 | 42dc347f4f22175101048617e1c17119c3856032a742cde9365342944cb9b624 |
Hashes for pyvpmr-240308-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f580bc40adf35991b7cfbf62ef97b2c17b8c4b315f38ed939fa3d5d3f9dbce92 |
|
MD5 | 7f80ba9dd387329b8342410d272781d8 |
|
BLAKE2b-256 | c2a5cede07a13c61924f753b94faa9461732b55c77bc35339a98a61241b9d13e |