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, --max-terms             <int>     number of terms (default: 10)
    -c, --max-exponent          <int>     maximum exponent (default: 4)
    -d, --precision-bits        <int>     number of precision bits (default: 512)
    -q, --quadrature-order      <int>     quadrature order (default: 500)
    -m, --precision-multiplier  <float>   precision multiplier (default: 1.5)
    -e, --tolerance             <float>   tolerance (default: 1E-8)
    -k, --kernel                <string>  file name of kernel function (default uses: exp(-t^2/4))
    -s, --singular-values                 print singular values
    -w, --weights                         print weights
    -h, --help                            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:
       terms = 30.
    exponent = 4.
   precision = 355.
 quad. order = 500.
  multiplier = 1.5000e+00.
   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+6.4089561283054790e-107j
-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: 3112 ms.

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-240921.tar.gz (2.4 MB view details)

Uploaded Source

Built Distributions

pyvpmr-240921-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-240921-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-240921-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-240921-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-240921-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-240921-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-240921.tar.gz.

File metadata

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

File hashes

Hashes for pyvpmr-240921.tar.gz
Algorithm Hash digest
SHA256 3a9177ed7a7bf2d9cef47974046f6f7690c750c9d660a5c60e26c8642532c644
MD5 ba4b8f977ca703c9b2bebb2f067a63ca
BLAKE2b-256 3034a0a96416309347257410028f878435570ab00ae2537ed5b74b75e889aa1b

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-240921-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 e0b8dc395adccfe75e34d11de8388e17bbb6d783b94c4a1f956ea77d53507bc0
MD5 abd9b2a6492dfbaf57e1131b5d109a2b
BLAKE2b-256 4a2b37d9543f26aebd8f0b2a5aebccab1cb2afa0eca33d69706d1f3b30b69dba

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-240921-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 e053b8cbb89ff3198f0e527a60a3fae0675ae83f0551bf7886942ba1869aff1a
MD5 ca0e1907b92179b67706e4344a21bea8
BLAKE2b-256 913300d81e029fd98c306e367d95030b2eb1d2de5b76f9561e0a43a8632d96a3

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-240921-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 2431839dd775152ff62650640e4c84111d5020c34435c3b597fa42ff67ffd503
MD5 1f686eac49428edc4864b77e4b8cb97a
BLAKE2b-256 f5f4b88f52189a2fd6a5c925e15b7e99b62467925fbd750b50536bb8121d085f

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-240921-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 67f4a03f62d14b7a59e8e1405a401ecd5ab3205d7df587dc26b6b8c6ca8c573f
MD5 8f30a21f3383c1ff3dda05681b6079c2
BLAKE2b-256 d9492df9f7cdb70ec6335b7c4cf559f92ac2c16565bf63459b8a27faa6560733

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-240921-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 baacaef90f2d438b65b4b287bf48ea39b04725a4608a648c43eb95b62ff56b3c
MD5 5f3170e9492cc6b3b23713ebe503d12c
BLAKE2b-256 4e161912774bf567bd3c585f5ad31f41dc581c525ba48d75f662f57c68460a9d

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-240921-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 6b40a3989cce0ab36e674419ca66ef530495f11ef629911dae8e90fdeaf92f4e
MD5 c9105b15b62674477d4d835ea2997c2b
BLAKE2b-256 993f2fe388add6aa3a704897289612186a72a7f82d95251f33c28f65dec8baab

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