Módulo determinante m

18

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).Zmmm

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.mZmm

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.m

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.

Valeriy Sokolov
fonte
3
O que você quer dizer com `` eficiente ''? O problema é claramente em . P
david
2
é uma constante fixa? Como é dado? m
Michael Blondin
2
O que você quer dizer com pequeno? Eles poderiam ser escritos em unário?
Michael Blondin
5
Ainda não entendi a pergunta. O determinante de uma matriz inteira pode ser calculado em tempo polinomial, para que você possa apenas pegar esse valor no módulo . Não há necessidade de realizar divisões em Z m ou encontrar a fatoração de m . mZmm
david
2
@ValeriySokolov: Isso é álgebra linear básica. Por exemplo, verifique o Problema 11.5.3 da Complexidade Computacional de Christos H. Papadimitriou.
Tsuyoshi Ito

Respostas:

15

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=p1e1pnenpieiei=1pieiei , você pode usar levantamento Hensel.

Markus Bläser
fonte
Obrigado! É como algo que eu estava procurando. Esta é uma prática comum para os determinantes? (referências são bem vindas).
Valeriy Sokolov
6
Estas são técnicas padrão da álgebra de computadores. Dê uma olhada em Modern Computer Algebra de von zur Gathen e Gerhard ou em qualquer outro livro sobre álgebra computacional. Para o seu problema específico, consulte também o seguinte artigo de Pan, Yu & Stewart comet.lehman.cuny.edu/vpan/pdf/pan146.pdf
Markus Bläser
17

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

Sasho Nikolov
fonte
Obrigado por sua resposta com link para um artigo muito interessante.
Valeriy Sokolov
Também acredito que existem algoritmos mais eficientes, já que os autores deste artigo resolveram um problema mais geral (para qualquer anel comutativo).
Valeriy Sokolov
por "existem", você quer dizer "conhecido" ou "existir" (mas ainda não foi encontrado)? é um palpite razoável, mas estou um pouco cético de que a estrutura do anel de intigores modulo um pequeno número composto possa ajudá-lo muito. se eu estiver errado, acho isso interessante.
Sasho Nikolov 27/02/2012
1
@ValeriySokolov para ser justo, uma vez que a resposta não responder à sua pergunta, você pode considerar a aceitá-lo (ou se você quiser esperar, possivelmente, melhores respostas que não seria razoável)
Suresh Venkat
@SashoNikolov Descobri que o Wolfram Mathematica de alguma forma calcula isso. Em "Notas de implementação", eles dizem: Det usa métodos modulares e redução de linha, construindo um resultado usando o teorema do restante chinês. Gostaria de saber exatamente o que eles fazem, mas uma pesquisa rápida não me deu nada. Quanto ao "pequeno composto ", isso significa apenas que quero considerar a complexidade de adições e multiplicações neste anel como O ( 1 ) . Ou seja, todos os fatores como O ( log m ) são considerados O ( 1 ) . mO(1)O(logm)O(1)
Valeriy Sokolov
11

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 AmA , 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×nZmO(nω) operações aritméticas sobre básico Zm (número inteiro adição, multiplicação, exponenciação, etc). Então,

Dada uma matriz , existe um algoritmo determinístico que calcula det ( A ) usando operações aritméticas básicas de O ( n ω ) sobre Z mAZmn×ndet(A)O(nω)Zm [1] .

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 mmm ! 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ω

Juan Bermejo Vega
fonte
não é que geralmente é denotado ω ? θω
Sasho Nikolov 27/02/2012
Talvez eu não conheça a notação mais comum para isso.
Juan Bermejo Vega
Eu acho que você está certo, vou mudar para ser "mainstream" #
Juan Bermejo Vega