Skip to main content

The VPMR Algorithm

Project description

VPMR C++ Implementation

DOI codecov PyPI version Docker

gplv3-or-later

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:

  1. gmp for multiple precision arithmetic
  2. mpfr for multiple-precision floating-point computations
  3. tbb for parallel computing

The following libraries are included:

  1. mpreal mpreal type C++ wrapper, included
  2. BigInt BigInt arbitrary large integer for combinatorial number, included
  3. Eigen for matrix decomposition, included
  4. exprtk for expression parsing, included
  5. 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 and mpfr on your own.

On RPM-based Linux distributions (using dnf), if you are:

  1. compiling the application from source (or wheels are not available), sudo dnf install -y gcc-c++ tbb-devel mpfr-devel gmp-devel
  2. 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 and exprtk, which depend on very heavy usage of templates. The compilation would take minutes and around 2 GB memory. You need to install libraries gmp, mpfr and tbb 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 .

Or you simply pull using the following command.

docker pull tlcfem/vpmr

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,k)$ and $2^{4n}$. The number of precision bits shall be at least $4n+\log_2C(4n,2n)$. 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.

exp(-t^2/4)

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

exp(-t^2/10)

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pyvpmr-240916.tar.gz (5.5 MB view details)

Uploaded Source

Built Distributions

pyvpmr-240916-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.2 MB view details)

Uploaded CPython 3.13 manylinux: glibc 2.17+ x86-64

pyvpmr-240916-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.2 MB view details)

Uploaded CPython 3.12 manylinux: glibc 2.17+ x86-64

pyvpmr-240916-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.2 MB view details)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

pyvpmr-240916-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.2 MB view details)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

pyvpmr-240916-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.2 MB view details)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

pyvpmr-240916-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.2 MB view details)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

File details

Details for the file pyvpmr-240916.tar.gz.

File metadata

  • Download URL: pyvpmr-240916.tar.gz
  • Upload date:
  • Size: 5.5 MB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.12.6

File hashes

Hashes for pyvpmr-240916.tar.gz
Algorithm Hash digest
SHA256 3e58dad56158465981e1d52f765557f161a2135de039b7baf408216ca04bfa0a
MD5 b7e7cfe8b046eb3cdbcdcfdff8e03af8
BLAKE2b-256 d1c4db691fa8d6317360ef716884b36f190a26ef1acac47f63f4bc7d330cd736

See more details on using hashes here.

File details

Details for the file pyvpmr-240916-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for pyvpmr-240916-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 9981b6aaf2ec186e8ab0ba43bc162c471b8727db54b50e8b1ecd0c3d2ba6f00a
MD5 18cc014e51a5e49bf65965eb7833f877
BLAKE2b-256 f826debddb014f5809d5386e8dd5666830f94396e8ffcdbbf9c68ed87a6bcccb

See more details on using hashes here.

File details

Details for the file pyvpmr-240916-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for pyvpmr-240916-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 3824a120e26a22d10910a7d69b2dc34641ca11fab2b34b77d813e998c694f01b
MD5 76a8e1702ef232e46acc49f052a0963b
BLAKE2b-256 0b796e0548bae68bda0a01f94798cceaf67668128678047d1517cb2fd17e4c99

See more details on using hashes here.

File details

Details for the file pyvpmr-240916-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for pyvpmr-240916-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 1979be61c1802a34f1cbf22849f4b04f95a828e55fa8e116b01da237b929b049
MD5 13ae63c4d7a054698f4444f69eef87ba
BLAKE2b-256 fb0f2148dd9196e3371c5f127872dd0f3ff7235222b8a7cb0fc529cc37ddd71c

See more details on using hashes here.

File details

Details for the file pyvpmr-240916-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for pyvpmr-240916-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 97098c862b18b8698284b0c8f79ec0d81e7cdbffe47f21d2b4b5064b88bb2989
MD5 62813ca67c5ff63243dc16d032958815
BLAKE2b-256 f80decc1e7ff7c7d760b4459493380042288a78e46f3ef68f143bfddb5e8beda

See more details on using hashes here.

File details

Details for the file pyvpmr-240916-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for pyvpmr-240916-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 04d533b06cc1197564a3b177bcc65f566a7c160f999eb9eb9b6fbf6216e8436d
MD5 8fe893193c1897a6aac752d52a52e1a5
BLAKE2b-256 806ad33f1c9fb7a0e30d992e38152e4b1917586690297d9ec7f16b5d208ef214

See more details on using hashes here.

File details

Details for the file pyvpmr-240916-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for pyvpmr-240916-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 53da42bb3067b3e3a5fcd30ac52dacc89739c68301061d9f44a94370d89f19ce
MD5 2d47ccb947be59496845244fdee50c66
BLAKE2b-256 0f8547595bdbc5a68b472a1df372cca61dca1d25373f7b68b2c19febf32f3cdd

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page