## RestrictProlong.jl

Efficient multigrid operators for Julia
Author timholy
Popularity
7 Stars
Updated Last
1 Year Ago
Started In
September 2016

# RestrictProlong

This package provides efficient multidimensional implementations of two operators, `restrict` and `prolong`, which feature heavily in multigrid methods. In general terms, these operations reduce and increase, respectively, the size of arrays by a factor of 2 along one or more dimensions. The two operators satisfy the "Galerkin condition," meaning that as operators they are transposes of one another.

In addition to being useful for mulitigrid methods, `restrict` can be used as a fast antialiasing thumbnail generator for images.

## Usage examples

Set up the following test array:

```julia> using RestrictProlong

julia> A = zeros(5,5); A[3,3] = 1
1

julia> A
5×5 Array{Float64,2}:
0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0
0.0  0.0  1.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0
0.0  0.0  0.0  0.0  0.0```

`restrict` reduces the size along the chosen dimension(s) (all dimensions are chosen if not specified), approximately preserving the mean value of the input array:

```julia> restrict(A)
3×3 Array{Float64,2}:
0.0  0.0   0.0
0.0  0.25  0.0
0.0  0.0   0.0```

After restriction, an axis with `l = size(A, d)` has size `(l+1) ÷ 2`.

For prolongation, it's best to specify the desired target size, which can be either `2l` or `2l-1`:

```julia> prolong(A, (10,10))
10×10 Array{Float64,2}:
0.0  0.0  0.0  0.0       0.0       0.0       0.0       0.0  0.0  0.0
0.0  0.0  0.0  0.0       0.0       0.0       0.0       0.0  0.0  0.0
0.0  0.0  0.0  0.0       0.0       0.0       0.0       0.0  0.0  0.0
0.0  0.0  0.0  0.015625  0.046875  0.046875  0.015625  0.0  0.0  0.0
0.0  0.0  0.0  0.046875  0.140625  0.140625  0.046875  0.0  0.0  0.0
0.0  0.0  0.0  0.046875  0.140625  0.140625  0.046875  0.0  0.0  0.0
0.0  0.0  0.0  0.015625  0.046875  0.046875  0.015625  0.0  0.0  0.0
0.0  0.0  0.0  0.0       0.0       0.0       0.0       0.0  0.0  0.0
0.0  0.0  0.0  0.0       0.0       0.0       0.0       0.0  0.0  0.0
0.0  0.0  0.0  0.0       0.0       0.0       0.0       0.0  0.0  0.0

julia> prolong(A, (9,10))
9×10 Array{Float64,2}:
0.0  0.0  0.0  0.0      0.0      0.0      0.0      0.0  0.0  0.0
0.0  0.0  0.0  0.0      0.0      0.0      0.0      0.0  0.0  0.0
0.0  0.0  0.0  0.0      0.0      0.0      0.0      0.0  0.0  0.0
0.0  0.0  0.0  0.03125  0.09375  0.09375  0.03125  0.0  0.0  0.0
0.0  0.0  0.0  0.0625   0.1875   0.1875   0.0625   0.0  0.0  0.0
0.0  0.0  0.0  0.03125  0.09375  0.09375  0.03125  0.0  0.0  0.0
0.0  0.0  0.0  0.0      0.0      0.0      0.0      0.0  0.0  0.0
0.0  0.0  0.0  0.0      0.0      0.0      0.0      0.0  0.0  0.0
0.0  0.0  0.0  0.0      0.0      0.0      0.0      0.0  0.0  0.0```

`prolong` approximately preserves the sum of the input array.