ShiftConvolve
is a R package which uses exponential shifting and the Fast Fourier Transformations (FFT) to compute the (right) tail of the Poisson Binomial Distribution.
This package makes use of the Fastest Fourier Transform in the West
(FFTW) library to perform the necessary DFT and Inverse DFT computations.
For the ShiftConvolve
implementation which uses minFFT to perform the Fourier Transformations please go to https://github.com/andrew12678/ShiftConvolve.
In the interest of speed we all significant computational aspects of our procedure are executed by code written in C and the R code mainly acts as a wrapper around that compiled C code.
We have successfully installed ShiftConvolveFFTW
on Windows 10: Professional Version 1909
, macOS: Mojave 10.14.6/Catalina 10.15.4
and Linux: Ubuntu 18.04/Manjaro 19.02 KDE Plasma
. A full installation guide will be provided below for all 3 Operating Systems.
ShiftConvolveFFTW
has also been installed on both AMD
and Intel
CPU systems. Specifically, a Intel Core i7 MacMini with 32GB of RAM
, AMD Ryzen 5 2600 with 16GB of RAM
and a Macbook Pro i7 with 16GB of RAM
As eluded to above, FFTW
will be a necessary dependency.
This package was originally compiled in an Ubuntu 18.04
Linux operating system using R 3.5.1
and FFTW 3.3.5
but was later recompiled (without any modification of the configurations) in a Manjaro 19.02 KDE Plasma
Linux operating system with inbuilt FFTW 3.3.8
and R 3.6.3
.
Since the FFTW
came along with the Manjaro
installation, we will only outline installations on the Ubuntu
and macOS
system which does not automatically install FFTW
.
For Ubuntu
the steps included:
wget http://fftw.org/fftw-3.3.5.tar.gz
tar -xzf fftw-3.3.5.tar.gz
cd fftw-3.3.5
./configure --enable-shared
make
sudo make install
Since the Manjaro
distribution came with FFTW 3.3.8
, later versions of FFTW
should be able to be installed as well.
FFTW should be first installed in the same manner as the Linux distributions with the macOS
terminal. For emphasis we repeat it below.
wget http://fftw.org/fftw-3.3.5.tar.gz
tar -xzf fftw-3.3.5.tar.gz
cd fftw-3.3.5
./configure --enable-shared
make
sudo make install
To use wget
, the user may have to install Homebrew, which can be installed with the following command.
/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install.sh)"
To avoid a further pkg-config
error later down the track, we shall install it with brew
brew install pkg-config
If the above throws an error then it should prompt you make the following 2 changes and then try the installation again.
sudo chown -R $(whoami) /usr/local/lib/pkgconfig /usr/local/share/info
chmod u+w /usr/local/lib/pkgconfig /usr/local/share/info
brew install pkg-config
Before installation, get to see if you have Rtools
installed on your system already (via Add or remove programs
). If not we wish to download and install here: https://cran.r-project.org/bin/windows/Rtools/
We will not be installing FFTW
in the conventional way for Windows
, instead we will use the precompiled binary called fftw-3.3.5-dll64.zip
found here: http://www.fftw.org/install/windows.html.
After unzipping fftw-3.3.5-dll64.zip
, we want to copy the files fftw3.h
and libfftw3-3.dll
to a directory C:\fftw
(to create this directory simply open any Windows File Explorer
, click This PC
on the left panel and enter Local Disk (C:) and just make a new folder called fftw
)
Then in the Windows
search bar we want to type environment
and then click: Edit the system environment variables
.
We then want to click Environment Variables
in the following pop-up:
Then under System Variables
click New
to add a variable for LIB_FFTW
with value C:\fftw
:
Then back to System Variables
we want to find the entry called Path
, click once on it to highlight it and then click Edit
:
Here we want to make sure the C:\Rtools\bin
and C:\fftw
are both entries are in Path, otherwise we add then by clicking New
:
That should conclude all the installation of FFTW
dependencies on Windows.
Alternatively, one could attempt to build FFTW
from source using MinGW
as outlined on http://www.fftw.org/install/windows.html using the commands in the MinGW
terminal in the directory of the zip file downloaded earlier:
./configure --with-our-malloc16 --with-windows-f77-mangling --enable-shared --disable-static --enable-threads --with-combined-threads --enable-portable-binary --enable-sse2 --with-incoming-stack-boundary=2
make
make install
However, we have not (and do not intend to) try this.
The most simple installation involves installing devtools
in R and using the install_github()
function.
install.packages('devtools') # If you have not installed devtools
devtools::install_github('https://github.com/andrew12678/ShiftConvolveFFTW.git')
An alternative installation procedure involves cloning the repository, creating a RStudio
project and then building.
An simple example with the uniform distribution
library(ShiftConvolvePoibin)
set.seed(18)
n=1000
probs <- runif(n)
x <- c(200, 500, 800)
p <- seq(0, 1, 0.01)
dpoisbin(x,probs,method="ShiftConvolve",log.p=FALSE)
ppoisbin(x,probs,method="ShiftConvolve",lower.tail=FALSE,log.p=TRUE)
qpoisbin(p,probs,method="ShiftConvolve",lower.tail=TRUE,log.p=FALSE)
rpoisbin(n,probs)
[1] Peres, N., Lee, A., and Keich, U. (2020). Exactly computing the tail of the Poisson-Binomial Distribution. arXiv:2004.07429