Complexidade de problemas multilineares - Rodriguez, Daniel Nelson Panario (1991)
Na area de complexidade algebrica tem-se estudado com muita profundidade como calcular o produto de dois elementos de uma algebra qualquer, os assim chamados problemas bilineares. Neste trabalho, estendemos o estudo ao produto de n elementos de uma algebra, o que chamamos de problemas multilineares. Apresentamos uma nova forma de definir e de caracterizar os algoritmos algebricos, mostramos cotas inferiores do problema de calcular um conjunto de funcoes em k ['X IND.1',...,'X IND.N'], definimos algoritmos multilineares, damos um gerador de algoritmos multilineares quase-otimos e estudamos com detalhe o produto de n polinomios numa variavel. Esses metodos se mostraram adequados para o produto de polinomios em varias variaveis densos. Os polinomios em varias variaveis esparsos sao muito importantes na pratica, sendo nosso modelo ineficiente para trata-los. Analisamos um algoritmo para calcular polinomios esparsos por interpolacao, comparando sua complexidade pelo modelo ram e pelo modelo de computacao multiplicativo