user
The convolution of two functions 

F
{\displaystyle {\displaystyle {\mathit {F}}}}
 and 

H
{\displaystyle {\displaystyle {\mathit {H}}}}
 of
an integer variable is defined as the function 

G
{\displaystyle {\displaystyle {\mathit {G}}}}
satisfying

:   G
    (
    n
    )
    =

    ∑

    m
    =
    −
    ∞

    ∞
    F
    (
    m
    )
    H
    (
    n
    −
    m
    )
    {\displaystyle {\displaystyle G(n)=\sum \_{m=-\infty }^{\infty }F(m)H(n-m)}}

for all integers 

n
{\displaystyle {\displaystyle {\mathit {n}}}}
. Assume 

F
(
n
)
{\displaystyle {\displaystyle F(n)}}
 can be non-zero only for 

0
{\displaystyle {\displaystyle 0}}
 ≤ 

n
{\displaystyle {\displaystyle {\mathit {n}}}}
 ≤ 

|


F

|
{\displaystyle {\displaystyle |{\mathit {F}}|}}
, where 

|


F

|
{\displaystyle {\displaystyle |{\mathit {F}}|}}
 is the "length" of 

F
{\displaystyle {\displaystyle {\mathit {F}}}}
, and similarly for 

G
{\displaystyle {\displaystyle {\mathit {G}}}}
 and 

H
{\displaystyle {\displaystyle {\mathit {H}}}}
, so that the functions can be modeled as finite sequences by identifying 

f

0
,

f

1
,

f

2
,
…
{\displaystyle {\displaystyle f\_{0},f\_{1},f\_{2},\dots }}
 with 

F
(
0
)
,
F
(
1
)
,
F
(
2
)
,
…
{\displaystyle {\displaystyle F(0),F(1),F(2),\dots }}
, etc.
Then for example, values of 

|


F

|
=
6
{\displaystyle {\displaystyle |{\mathit {F}}|=6}}
 and 

|


H

|
=
5
{\displaystyle {\displaystyle |{\mathit {H}}|=5}}
 would determine the following value of 

g
{\displaystyle {\displaystyle {\mathit {g}}}}
 by definition.

:   g

    0

    =


    f

    0

    h

    0

    g

    1

    =


    f

    1

    h

    0

    +


    f

    0

    h

    1

    g

    2

    =


    f

    2

    h

    0

    +


    f

    1

    h

    1

    +


    f

    0

    h

    2

    g

    3

    =


    f

    3

    h

    0

    +


    f

    2

    h

    1

    +


    f

    1

    h

    2

    +


    f

    0

    h

    3

    g

    4

    =


    f

    4

    h

    0

    +


    f

    3

    h

    1

    +


    f

    2

    h

    2

    +


    f

    1

    h

    3

    +


    f

    0

    h

    4

    g

    5

    =


    f

    5

    h

    0

    +


    f

    4

    h

    1

    +


    f

    3

    h

    2

    +


    f

    2

    h

    3

    +


    f

    1

    h

    4

    g

    6

    =

    f

    5

    h

    1

    +


    f

    4

    h

    2

    +


    f

    3

    h

    3

    +


    f

    2

    h

    4

    g

    7

    =

    f

    5

    h

    2

    +


    f

    4

    h

    3

    +


    f

    3

    h

    4

    g

    8

    =

    f

    5

    h

    3

    +


    f

    4

    h

    4

    g

    9

    =

    f

    5

    h

    4
    {\displaystyle {\displaystyle {\begin{array}{lllllllllll}g\_{0}&=&f\_{0}h\_{0}\\g\_{1}&=&f\_{1}h\_{0}&+&f\_{0}h\_{1}\\g\_{2}&=&f\_{2}h\_{0}&+&f\_{1}h\_{1}&+&f\_{0}h\_{2}\\g\_{3}&=&f\_{3}h\_{0}&+&f\_{2}h\_{1}&+&f\_{1}h\_{2}&+&f\_{0}h\_{3}\\g\_{4}&=&f\_{4}h\_{0}&+&f\_{3}h\_{1}&+&f\_{2}h\_{2}&+&f\_{1}h\_{3}&+&f\_{0}h\_{4}\\g\_{5}&=&f\_{5}h\_{0}&+&f\_{4}h\_{1}&+&f\_{3}h\_{2}&+&f\_{2}h\_{3}&+&f\_{1}h\_{4}\\g\_{6}&=&&&f\_{5}h\_{1}&+&f\_{4}h\_{2}&+&f\_{3}h\_{3}&+&f\_{2}h\_{4}\\g\_{7}&=&&&&&f\_{5}h\_{2}&+&f\_{4}h\_{3}&+&f\_{3}h\_{4}\\g\_{8}&=&&&&&&&f\_{5}h\_{3}&+&f\_{4}h\_{4}\\g\_{9}&=&&&&&&&&&f\_{5}h\_{4}\end{array}}}}

We can write this in matrix form as:

:   (

    g

    0

    g

    1

    g

    2

    g

    3

    g

    4

    g

    5

    g

    6

    g

    7

    g

    8

    g

    9
    )
    =

    (

    f

    0

    f

    1


    f

    0

    f

    2


    f

    1


    f

    0

    f

    3


    f

    2


    f

    1


    f

    0

    f

    4


    f

    3


    f

    2


    f

    1


    f

    0

    f

    5


    f

    4


    f

    3


    f

    2


    f

    1

    f

    5


    f

    4


    f

    3


    f

    2

    f

    5


    f

    4


    f

    3

    f

    5


    f

    4

    f

    5
    )


    (

    h

    0

    h

    1

    h

    2

    h

    3

    h

    4
    )
    {\displaystyle {\displaystyle \left({\begin{array}{l}g\_{0}\\g\_{1}\\g\_{2}\\g\_{3}\\g\_{4}\\g\_{5}\\g\_{6}\\g\_{7}\\g\_{8}\\g\_{9}\\\end{array}}\right)=\left({\begin{array}{lllll}f\_{0}\\f\_{1}&f\_{0}\\f\_{2}&f\_{1}&f\_{0}\\f\_{3}&f\_{2}&f\_{1}&f\_{0}\\f\_{4}&f\_{3}&f\_{2}&f\_{1}&f\_{0}\\f\_{5}&f\_{4}&f\_{3}&f\_{2}&f\_{1}\\&f\_{5}&f\_{4}&f\_{3}&f\_{2}\\&&f\_{5}&f\_{4}&f\_{3}\\&&&f\_{5}&f\_{4}\\&&&&f\_{5}\end{array}}\right)\;\left({\begin{array}{l}h\_{0}\\h\_{1}\\h\_{2}\\h\_{3}\\h\_{4}\\\end{array}}\right)}}

or

:   g
    =
    A

    h
    {\displaystyle {\displaystyle g=A\;h}}

For this task, implement a function (or method, procedure, subroutine, etc.) `deconv` to perform *deconvolution* (i.e., the *inverse* of convolution) by constructing and solving such a system of equations represented by the above matrix 

A
{\displaystyle {\displaystyle A}}
 for 

h
{\displaystyle {\displaystyle {\mathit {h}}}}
 given 

f
{\displaystyle {\displaystyle {\mathit {f}}}}
 and 

g
{\displaystyle {\displaystyle {\mathit {g}}}}
.

* The function should work for 

  G
  {\displaystyle {\displaystyle {\mathit {G}}}}
   of arbitrary length (i.e., not hard coded or constant) and 

  F
  {\displaystyle {\displaystyle {\mathit {F}}}}
   of any length up to that of 

  G
  {\displaystyle {\displaystyle {\mathit {G}}}}
  . Note that 

  |


  H

  |
  {\displaystyle {\displaystyle |{\mathit {H}}|}}
   will be given by 

  |


  G

  |
  −

  |


  F

  |
  +
  1
  {\displaystyle {\displaystyle |{\mathit {G}}|-|{\mathit {F}}|+1}}
  .
* There may be more equations than unknowns. If convenient, use a function from a library that finds the best fitting solution to an overdetermined system of linear equations (as in the Multiple regression task). Otherwise, prune the set of equations as needed and solve as in the Reduced row echelon form task.
* Test your solution on the following data. Be sure to verify both that `deconv`

  (
  g
  ,
  f
  )
  =
  h
  {\displaystyle {\displaystyle (g,f)=h}}
   and `deconv`

  (
  g
  ,
  h
  )
  =
  f
  {\displaystyle {\displaystyle (g,h)=f}}
   and display the results in a human readable form.

`h = [-8,-9,-3,-1,-6,7]  
f = [-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1]  
g = [24,75,71,-34,3,22,-45,23,245,25,52,25,-67,-96,96,31,55,36,29,-43,-7]`
assistant
(formerly Perl 6)

Translation of Python, using a modified version of the subroutine `rref` from Reduced row echelon form task.

```
sub deconvolve (@g, @f) {
    my \h = 1 + @g - @f;
    my @m;
    @m[^@g;^h] »+=» 0;
    @m[^@g; h] »=«  @g;
    for ^h -> \j { for @f.kv -> \k, \v { @m[j+k;j] = v } }
    (rref @m)[^h;h]
}

sub convolve (@f, @h) {
    my @g = 0 xx + @f + @h - 1;
    @g[^@f X+ ^@h] »+=« (@f X× @h);
    @g
}
 
# Reduced Row Echelon Form simultaneous equation solver
# Can handle over-specified systems of equations (N unknowns in N + M equations)
sub rref (@m) {
    @m = trim-system @m;
    my ($lead, $rows, $cols) = 0, @m, @m[0];
    for ^$rows -> $r {
        return @m unless $lead < $cols;
        my $i = $r;
        until @m[$i;$lead] {
            next unless ++$i == $rows;
            $i = $r;
            return @m if ++$lead == $cols;
        }
        @m[$i, $r] = @m[$r, $i] if $r != $i;
        @m[$r] »/=» $ = @m[$r;$lead];
        for ^$rows -> $n {
            next if $n == $r;
            @m[$n] »-=» @m[$r] »×» (@m[$n;$lead] // 0);
        }
        ++$lead;
    }
    @m
 }

# Reduce to N equations in N unknowns; a no-op unless rows > cols
sub trim-system (@m) {
    return @m unless @m ≥ @m[0]; 
    my (\vars, @t) = @m[0] - 1;
    for ^vars -> \lead {
        for ^@m -> \row {
            @t.append: @m.splice(row, 1) and last if @m[row;lead];
        }
    }
    while @t < vars and @m { @t.push: shift @m }
    @t
}
  
my @h = (-8,-9,-3,-1,-6,7);
my @f = (-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1);
my @g = (24,75,71,-34,3,22,-45,23,245,25,52,25,-67,-96,96,31,55,36,29,-43,-7);
 
.say for ~@g,   ~convolve(@f, @h),'';
.say for ~@h, ~deconvolve(@g, @f),'';
.say for ~@f, ~deconvolve(@g, @h),'';

```

Output:

```
24 75 71 -34 3 22 -45 23 245 25 52 25 -67 -96 96 31 55 36 29 -43 -7
24 75 71 -34 3 22 -45 23 245 25 52 25 -67 -96 96 31 55 36 29 -43 -7

-8 -9 -3 -1 -6 7
-8 -9 -3 -1 -6 7

-3 -6 -1 8 -6 3 -1 -9 -9 3 -2 5 2 -2 -7 -1
-3 -6 -1 8 -6 3 -1 -9 -9 3 -2 5 2 -2 -7 -1
```