README.md 6.42 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
14
15
16
17
18
19


Installation
------------

### Requirements

- [Python 3](https://www.python.org/)
- [pybind11](https://github.com/pybind/pybind11)
Martin Reinecke's avatar
Martin Reinecke committed
20
21
- a C++17-capable C++ compiler (tested with g++ version 7 or newer and clang++;
  recent versions of MSVC on Windows also work, but are tested less frequently)
Martin Reinecke's avatar
Martin Reinecke committed
22
23
24

### Sources

Martin Reinecke's avatar
Martin Reinecke committed
25
The latest version of DUCC can be obtained by cloning the repository via
Martin Reinecke's avatar
Martin Reinecke committed
26
27
28
29
30
31
32
33
34
35
36
37
38

    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
Martin Reinecke committed
39
40
41
42
43
NOTE: compilation of the code will take a sinificant amount of time
(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
44

Martin Reinecke's avatar
Martin Reinecke committed
45
46
47
48
49
50
51
52
Installing multiple versions simultaneously
===========================================

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
53
module name itself (the module is not called "ducc", but rather "ducc<X>"),
Martin Reinecke's avatar
Martin Reinecke committed
54
55
56
57
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
58
the latest incarnation of DUCC 0, this will be on branch "ducc0" of the
Martin Reinecke's avatar
Martin Reinecke committed
59
60
61
62
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
63
64


Martin Reinecke's avatar
Martin Reinecke committed
65
66
67
68
69
70
71
DUCC components
===============

ducc.fft
--------

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

The central algorithms are derived from Paul Swarztrauber's FFTPACK code
(http://www.netlib.org/fftpack).

Martin Reinecke's avatar
Martin Reinecke committed
78
### Features
Martin Reinecke's avatar
Martin Reinecke committed
79
80
81
82
83
84
85
86
87
88
- 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
89
### Design decisions and performance characteristics
Martin Reinecke's avatar
Martin Reinecke committed
90
91
92
93
94
- 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
95
  FFTW_MEASURE; in single precision `ducc.fft` can be significantly faster.
Martin Reinecke's avatar
Martin Reinecke committed
96
97
98
99
100

ducc.sht
--------

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


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

Martin Reinecke's avatar
Martin Reinecke committed
109
This library provides Python bindings for the most important functionality
Martin Reinecke's avatar
Martin Reinecke committed
110
related to the HEALPix tesselation (<https://arxiv.org/abs/astro-ph/0409513>),
Martin Reinecke's avatar
Martin Reinecke committed
111
112
113
114
115
except for spherical harmonic transforms, which are covered vy `ducc.sht`.

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
116
117
118
119
120
121
122
123
124
125
- 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
126
This code has evolved from the original `totalconvolver` algorithm described
Martin Reinecke's avatar
Martin Reinecke committed
127
in <https://arxiv.org/abs/astro-ph/0008227> via the `conviqt` code
Martin Reinecke's avatar
Martin Reinecke committed
128
(<https://arxiv.org/abs/1002.1050>).
Martin Reinecke's avatar
Martin Reinecke committed
129

Martin Reinecke's avatar
Martin Reinecke committed
130

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


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

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

Martin Reinecke's avatar
Martin Reinecke committed
147
### Programming aspects
Martin Reinecke's avatar
Martin Reinecke committed
148
- shared-memory parallelization via standard C++ threads.
Martin Reinecke's avatar
Martin Reinecke committed
149
150
151
- 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
152
### Numerical aspects
Martin Reinecke's avatar
Martin Reinecke committed
153
- uses the analytical gridding kernel presented in
Martin Reinecke's avatar
Martin Reinecke committed
154
  <https://arxiv.org/abs/1808.06736>
Martin Reinecke's avatar
Martin Reinecke committed
155
- uses the "improved W-stacking method" described in
Martin Reinecke's avatar
Martin Reinecke committed
156
  <https://www.repository.cam.ac.uk/handle/1810/292298> (p. 139ff)
Martin Reinecke's avatar
Martin Reinecke committed
157
158
159
- 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
160
161
162
163
164
165
166
167


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

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