Quais são os algoritmos eficientes conhecidos para calcular um determinante de uma matriz inteira com coeficientes em , o anel de resíduos módulo m . O número m pode não ser primo, mas composto (portanto, os cálculos são realizados em anel, não em um campo).
Até onde eu sei (leia abaixo), a maioria dos algoritmos são modificações da eliminação gaussiana. A questão é sobre a eficiência computacional desses procedimentos.
Se aconteceu que existe uma abordagem diferente, eu também estou curioso.
Desde já, obrigado.
Atualizar:
Deixe-me explicar a fonte desta pergunta. Suponha que é um número primo. Então Z m é um campo. E, neste caso, podemos realizar todos os cálculos usando números menores que m , portanto, temos um bom limite superior em todas as operações em números: adição, multiplicação e inversão - todas as operações necessárias para executar a eliminação gaussiana.
Por outro lado, não podemos realizar inversão para alguns números, caso não seja primo. Então, precisamos de alguns truques para calcular determinantes.
E agora estou curioso para saber quais são os truques conhecidos para fazer o trabalho e se esses truques podem ser encontrados nos papéis dos livros.
fonte
Respostas:
Se você sabe a fatoração de você pode calcular modulo cada p e i i separadamente e depois combinar os resultados usando remaindering chinês. Se e i = 1 , então computação modulo p o e i i é fácil, uma vez que este é um campo. Para maiores e im=pe11⋯penn peii ei=1 peii ei , você pode usar levantamento Hensel.
fonte
Existe um algoritmo combinatório de Mahajan e Vinay que funciona sobre anéis comutativos: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html
fonte
Para resolver esse problema, existe um algoritmo determinístico rápido baseado nas formas normais de Smith, cuja pior complexidade é limitada pelo custo da multiplicação de matrizes sobre o número inteiro do módulo . Para qualquer matriz Am A , o algoritmo gera sua forma normal de Smith, de onde pode ser facilmente calculado.det(A)
Mais concretamente, define de modo que dois n × n matrizes com coeficientes tomadas a partir de Z m pode ser multiplicado usando S ( n ω )ω n×n Zm O(nω) operações aritméticas sobre básico Zm (número inteiro adição, multiplicação, exponenciação, etc). Então,
Quando isso foi escrito em 1996, não havia alternativa assintoticamente mais rápida (o artigo menciona a existência anterior de algoritmos com o mesmo limite, mas não sei quais, ou se são probabilísticos).
Atualização (17 de julho de 2013): um recurso interessante desse algoritmo é que ele é executado em tempo polinomial para o composto arbitrário sem conhecer uma fatoração prima-nuber de mm m ! Isso é bom, pois não há algoritmos eficientes (clássicos) conhecidos para fatoração (é claro, se você tivesse um computador quântico, poderia aplicar o algoritmo de Shor ). Se você fazer tem a fatoração, em seguida, o algoritmo Markus sugeriu parece maneira mais simples de implementar.
Notas: no artigo, a complexidade das "operações aritméticas básicas" é se você usar aritmética inteira padrão, mas é possível obter O ( M ( log m ) log log m ) com técnicas mais rápidas. M ( t ) limita o custo de multiplicar dois inteiros de t- bits. O registro atual para ω é 2,3727 .O(log2m) O(M(logm)loglogm) M(t) t ω
fonte