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
# or using GitHub Container Registry
docker pull ghcr.io/tlcfem/vmpr

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

Uploaded Source

Built Distributions

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

File metadata

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

File hashes

Hashes for pyvpmr-241011.tar.gz
Algorithm Hash digest
SHA256 a194b402516377060bc6f7b329612bfff65aebf02f6d3b9cca5772faecf98927
MD5 8fc6e86cd0d3d59126bf92d3b6013756
BLAKE2b-256 6a75e8a23a9562669140dc96ff8f9b84e782860952f211ec00f0a0afbeeb4cf2

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-241011-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 c6d15a3d3acc4c5e95507169383ac3c218f54ce77b7fcb5acec8a2fd2a411b45
MD5 ecfde6acebcdf8d83940844d58b2dbe8
BLAKE2b-256 5b2c0a217814c8a4557e9091b3e54ae1fc77784c6776e6e4e1caa85e225206e2

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-241011-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 0a1d783c328a585d7aa36e470a09e179b9e727ba5b47638060e0edd55d1448cd
MD5 04ff4d4f04f8ca4658f1da9852c729d4
BLAKE2b-256 643704a80677011bb1857a096710b3279667174488194603bb2c00a496322dc3

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-241011-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 ec5ced423423e821e7ef8704d8ea6d64fb8ff9de998274e5109a87d53daa9f4f
MD5 069e18666530d88df08b5cf5e19aacf1
BLAKE2b-256 b63a7cfe6660ef1233c68df929fc67a0e7f606a9c30d0ca2edbda23d47066cc9

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-241011-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 2b483e761246b0709f8ef4cc46b2fe1a9622ac639a174bb8459f6a80644b9ecd
MD5 96c0bd37628b847e31fa207878321cda
BLAKE2b-256 a17c454415100c2f21120445fb0abb9ca18aa9ffa06f879d17fe3d82eed9a2e8

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-241011-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 f2cf1f7afe873700764e0f8187170053c1a33b2cfa4874a02042b9dd7dcdc195
MD5 d0fba0a0752b154d4f4aeb2a8072e212
BLAKE2b-256 1e9fe74f77aa95a01d1d846b951e01d56ca3e44dfb31c642ebb82b0bab444af9

See more details on using hashes here.

File details

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

File metadata

File hashes

Hashes for pyvpmr-241011-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 bd5146af587cb9a5b4eb9575ed23d32cf3fc988464152ea4356fbd940effa551
MD5 0237efb8e21b8951b734c68c7c422576
BLAKE2b-256 8116901c02dc5bbfc0b4ffac4848ede005a4afa171ddca8dac4ad6170dc74533

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