README.md 6.38 KB
Newer Older
Martin Reinecke's avatar
Martin Reinecke committed
1 2
Distinctly Useful Code Collection (DUCC)
========================================
Martin Reinecke's avatar
Martin Reinecke committed
3

Martin Reinecke's avatar
Martin Reinecke committed
4 5 6 7
This is a collection of basic programming tools for numerical computation,
including Fast Fourier Transforms, Spherical Harmonic Transforms, non-equispaced
Fourier transforms, as well as some concrete applications like 4pi convolution
on the sphere and gridding/degridding of radio interferometry data.
Martin Reinecke's avatar
Martin Reinecke committed
8

Martin Reinecke's avatar
Martin Reinecke committed
9 10
The code is written in C++17, but provides a simple and comprehensive Python
interface.
Martin Reinecke's avatar
Martin Reinecke committed
11 12 13

### Requirements

Martin Reinecke's avatar
Martin Reinecke committed
14
- [Python >= 3.6](https://www.python.org/)
Martin Reinecke's avatar
Martin Reinecke committed
15
- [pybind11](https://github.com/pybind/pybind11)
Martin Reinecke's avatar
typo  
Martin Reinecke committed
16
- a C++17-capable compiler (tested with g++ version 7 or newer and clang++;
Martin Reinecke's avatar
Martin Reinecke committed
17
  recent versions of MSVC on Windows also work, but are tested less frequently)
Martin Reinecke's avatar
Martin Reinecke committed
18 19 20

### Sources

Martin Reinecke's avatar
Martin Reinecke committed
21
The latest version of DUCC can be obtained by cloning the repository via
Martin Reinecke's avatar
Martin Reinecke committed
22 23 24 25 26 27 28 29 30 31 32 33 34

    git clone https://gitlab.mpcdf.mpg.de/mtr/ducc.git

### Installation

In the following, we assume a Debian-based distribution. For other
distributions, the "apt" lines will need slight changes.

DUCC and its mandatory dependencies can be installed via:

    sudo apt-get install git python3 python3-pip python3-dev python3-pybind11 pybind11-dev
    pip3 install --user git+https://gitlab.mpcdf.mpg.de/mtr/ducc.git

Martin Reinecke's avatar
typo  
Martin Reinecke committed
35
NOTE: compilation of the code will take a significant amount of time
Martin Reinecke's avatar
Martin Reinecke committed
36 37 38 39
(several minutes). Binary packages are deliberately not made available, since
much better performance can be achieved by compiling the code specifically for
the detected target CPU.

Martin Reinecke's avatar
Martin Reinecke committed
40

Martin Reinecke's avatar
Martin Reinecke committed
41
Installing multiple versions simultaneously
Martin Reinecke's avatar
Martin Reinecke committed
42
-------------------------------------------
Martin Reinecke's avatar
Martin Reinecke committed
43 44 45 46 47 48

The interfaces of the DUCC components are expected to evolve over time; whenever
an interface changes in a manner that is not backwards compatible, the DUCC
version number will increase. As a consequence it might happen that one part of
a Python code may use an older version of DUCC while at the same time another
part requires a newer version. Since DUCC's version number is included in the
Martin Reinecke's avatar
Martin Reinecke committed
49
module name itself (the module is not called `ducc`, but rather `ducc<X>`),
Martin Reinecke's avatar
Martin Reinecke committed
50 51 52 53
this is not a problem, as multiple DUCC versions can be installed
simultaneously.
The latest patch levels of a given DUCC version will always be available at the
HEAD of the git branch with the respective name. In other words, if you need
Martin Reinecke's avatar
fixes  
Martin Reinecke committed
54
the latest incarnation of DUCC 0, this will be on branch "ducc0" of the
Martin Reinecke's avatar
Martin Reinecke committed
55 56 57 58
git repository, and it will be installed as the package "ducc0".
Later versions will be maintained on new branches and will be installed as
"ducc1" and "ducc2", so that there will be no conflict with potentially
installed older versions.
Martin Reinecke's avatar
Martin Reinecke committed
59 60


Martin Reinecke's avatar
Martin Reinecke committed
61 62 63 64 65 66 67
DUCC components
===============

ducc.fft
--------

This package provides Fast Fourier, trigonometric and Hartley transforms with a
Martin Reinecke's avatar
Martin Reinecke committed
68
simple Python interface. It is an evolution of `pocketfft` and `pypocketfft`
Martin Reinecke's avatar
Martin Reinecke committed
69
which are currently used by `numpy` and `scipy`.
Martin Reinecke's avatar
Martin Reinecke committed
70

Martin Reinecke's avatar
Martin Reinecke committed
71 72
The central algorithms are derived from Paul Swarztrauber's
[FFTPACK](http://www.netlib.org/fftpack) code.
Martin Reinecke's avatar
Martin Reinecke committed
73

Martin Reinecke's avatar
Martin Reinecke committed
74
### Features
Martin Reinecke's avatar
Martin Reinecke committed
75 76 77 78 79 80 81 82 83 84
- supports fully complex and half-complex (i.e. complex-to-real and
  real-to-complex) FFTs, discrete sine/cosine transforms and Hartley transforms
- achieves very high accuracy for all transforms
- supports multidimensional arrays and selection of the axes to be transformed
- supports single, double, and long double precision
- makes use of CPU vector instructions when performing 2D and higher-dimensional
  transforms
- supports prime-length transforms without degrading to O(N**2) performance
- has optional multi-threading support for multidimensional transforms

Martin Reinecke's avatar
Martin Reinecke committed
85
### Design decisions and performance characteristics
Martin Reinecke's avatar
Martin Reinecke committed
86 87 88 89 90
- there is no internal caching of plans and twiddle factors, making the
  interface as simple as possible
- 1D transforms are significantly slower than those provided by FFTW (if FFTW's
  plan generation overhead is ignored)
- multi-D transforms in double precision perform fairly similar to FFTW with
Martin Reinecke's avatar
Martin Reinecke committed
91
  FFTW_MEASURE; in single precision `ducc.fft` can be significantly faster.
Martin Reinecke's avatar
Martin Reinecke committed
92 93 94 95 96

ducc.sht
--------

This package provides efficient spherical harmonic trasforms (SHTs). Its code
Martin Reinecke's avatar
Martin Reinecke committed
97
is derived from [libsharp](https://arxiv.org/abs/1303.4945), with accelerated
Martin Reinecke's avatar
Martin Reinecke committed
98
recurrence algorithms presented in
Martin Reinecke's avatar
Martin Reinecke committed
99
<https://www.jstage.jst.go.jp/article/jmsj/96/2/96_2018-019/_pdf>.
Martin Reinecke's avatar
Martin Reinecke committed
100 101 102 103 104


ducc.healpix
------------

Martin Reinecke's avatar
Martin Reinecke committed
105
This library provides Python bindings for the most important functionality
Martin Reinecke's avatar
Martin Reinecke committed
106 107
related to the [HEALPix](https://arxiv.org/abs/astro-ph/0409513) tesselation,
except for spherical harmonic transforms, which are covered by `ducc.sht`.
Martin Reinecke's avatar
Martin Reinecke committed
108 109 110 111

The design goals are
- similarity to the interface of the HEALPix C++ library
  (while respecting some Python peculiarities)
Martin Reinecke's avatar
Martin Reinecke committed
112 113 114 115 116 117 118 119 120 121
- simplicity (no optional function parameters)
- low function calling overhead


ducc.totalconvolve
------------------

Library for high-accuracy 4pi convolution on the sphere, which generates a
total convolution data cube from a set of sky and beam `a_lm` and computes
interpolated values for a given list of detector pointings.
Martin Reinecke's avatar
Martin Reinecke committed
122 123
This code has evolved from the original
[totalconvolver](https://arxiv.org/abs/astro-ph/0008227) algorithm described
Martin Reinecke's avatar
Martin Reinecke committed
124
via the [conviqt](https://arxiv.org/abs/1002.1050) code.
Martin Reinecke's avatar
Martin Reinecke committed
125

Martin Reinecke's avatar
Martin Reinecke committed
126

Martin Reinecke's avatar
Martin Reinecke committed
127
### Algorithmic details:
Martin Reinecke's avatar
Martin Reinecke committed
128
- the code uses `ducc.sht` SHTs and `ducc.fft` FFTs to compute the data cube
Martin Reinecke's avatar
Martin Reinecke committed
129 130
- shared-memory parallelization is provided via standard C++ threads.
- for interpolation, the algorithm and kernel described in
Martin Reinecke's avatar
Martin Reinecke committed
131
  <https://arxiv.org/abs/1808.06736> are used. This allows very efficient
Martin Reinecke's avatar
Martin Reinecke committed
132 133 134 135 136 137
  interpolation with user-adjustable accuracy.


ducc.wgridder
-------------

Martin Reinecke's avatar
Martin Reinecke committed
138
Library for high-accuracy gridding/degridding of radio interferometry datasets.
Martin Reinecke's avatar
Martin Reinecke committed
139 140 141
An earlier version of this code has been integrated into
[wsclean](https://sourceforge.net/projects/wsclean/)
(<https://arxiv.org/abs/1407.1943>)
Martin Reinecke's avatar
Martin Reinecke committed
142
as the `wgridder` component.
Martin Reinecke's avatar
Martin Reinecke committed
143

Martin Reinecke's avatar
Martin Reinecke committed
144
### Programming aspects
Martin Reinecke's avatar
Martin Reinecke committed
145
- shared-memory parallelization via standard C++ threads.
Martin Reinecke's avatar
Martin Reinecke committed
146 147 148
- kernel computation is performed on the fly, avoiding inaccuracies
  due to table lookup and reducing overall memory bandwidth

Martin Reinecke's avatar
Martin Reinecke committed
149
### Numerical aspects
Martin Reinecke's avatar
Martin Reinecke committed
150
- uses the analytical gridding kernel presented in
Martin Reinecke's avatar
Martin Reinecke committed
151
  <https://arxiv.org/abs/1808.06736>
Martin Reinecke's avatar
Martin Reinecke committed
152
- uses the "improved W-stacking method" described in
Martin Reinecke's avatar
Martin Reinecke committed
153
  <https://www.repository.cam.ac.uk/handle/1810/292298> (p. 139ff)
Martin Reinecke's avatar
Martin Reinecke committed
154 155 156
- in combination these two aspects allow extremely accurate gridding/degridding
  operations (L2 error compared to explicit DFTs can go below 1e-12) with
  reasonable resource consumption
157 158 159 160 161 162 163 164


ducc.misc
---------

Various unsorted functionality which will hopefully be categorized in the
future.