Fourier Transform

A Fourier Transform é descrita pelo somatório:

Porém, podemos reescrever na forma 'Ax = b':

Onde cada elemento da matriz M é:

E o vetor x é composto por valores incrementais de uma função periódica F:

Podemos então definir uma função DFT que recebe um vetor com os valores da função periódica, e retorna um vetor com o resultado da transformação:

function DFT(arr) {

Primeiro, pegamos o tamanho do vetor de valores:

    const N = arr.length;

E então criamos um novo vetor de tamanho N com valores incrementais. Isto é, com N = 512, temos um vetor [ 0, 1, 2, …, 510, 511 ]:

    let n = math.range(0, N)._data;

O método de utilizar math.range(0, N) de math.js foi testado e é mais rápido que utilizar outras maneiras de criar um array sequencial, como [...Array(SIZE).keys()].

Então, criamos uma matriz de tamanho 1×N com os valores de n. Isto é, para o vetor N = 512 anterior, agora temos [ [0], [1], [2], ..., [510], [511] ]:

    let k = n.map(e=>[e]);

Em seguida, calculamos o produto de k·n, fazendo a seguinte multiplicação:

    let exp = product(k, n);

Precisamos agora calcular

Como já fizemos k·n, só nos resta multiplicar cada elemento por -2π / N:

    exp = exp.map(row => row.map(el => -τ * el / N));

Então, fazemos

para cada item da matriz, utilizando a biblioteca math.js para calcular números complexos.

    const M = exp.map(row => row.map(
            el =>  math.exp(math.complex(0, el))
        )
    );

Com isso, temos a matriz M. Só nos resta fazer M·x e retornar o resultado:

    return math.multiply(M, arr);
}

Juntando tudo, nosso código fica:

const π = Math.PI;
const τ = 2*π;

function DFT(arr) {
    const N = arr.length;
    let n = math.range(0, N)._data;
    let k = n.map(e=>[e]);
    let exp = product(k, n);
    exp = exp.map(row => row.map(el => -τ * el / N));
    const M = exp.map(row => row.map(
            el =>  math.exp(math.complex(0, el))
        )
    );
    return math.multiply(M, arr);
}

Como entrada, usamos a seguinte expressão:

const arr = math.range(0, SIZE)._data.map(F);

para alguma função F e algum tamanho SIZE, definidos separadamente. Isso gerará um vetor com tamanho definido, preenchido com valores de F(t) para t sequencial.

Antes de decidir utilizar a biblioteca math.js, tinha implementado uma versão própria, ingênua e possivelmente ineficiente de multiplicação de vetores, para fazer k·n:

function product(A, B) {
    let out = [];
    for(let i = A.length-1; i >= 0; i--) {
        out[i] = [];
        for (let j = B.length - 1; j >= 0; j--) {
            out[i][j] = A[i] * B[j];
        }
    }
    return out;
}

Porém, após alguns testes, minha versão aparenta ser praticamente tão veloz quanto a implementada pela biblioteca, então decidi deixá-la.