Algoritmos para decomposição em frações parciais e integração de funções racionais

Algoritmos para decomposição simbólica em frações parciais e integração indefinida de funções racionais são descritos. Dois tipos de decomposição em frações parciais são investigados: frações parciais sem quadrados e frações parciais completas sem quadrados. Um método é derivado, com base na solução de um sistema linear, que produz a decomposição sem quadrados de qualquer função racional, digamos A/B. O tempo de computação é mostrado como O (n (In nf)) onde deg (A) < deg (B) = n e f é um número que está intimamente relacionado ao tamanho dos coeficientes que ocorrem em A e B. A decomposição completa em frações parciais sem quadrados pode então ser obtida diretamente e é mostrado que o tempo de computação para esse processo também é limitado por O (n (In nf)). Uma análise minuciosa é então feita do método clássico para funções racionais, devido a Hermite. É mostrado que a implementação mais eficiente deste método tem um tempo de computação de O (k n (In nc)), onde c é um número intimamente relacionado a f e k é o número de fatores sem quadrados de B. Um novo método é então apresentado que evita totalmente o uso da decomposição em frações parciais e em vez disso se baseia na solução de um sistema linear facilmente obtido. A análise teórica mostra que o tempo de computação para este método é O (n (In nf)) e testes extensivos substanciam sua superioridade sobre o método de Hermite.