Déterminant d'une matrice de Vandermonde généralisée

La matrice de Moore est similaire à la matrice de Vandermonde mais a une définition légèrement modifiée. http://en.wikipedia.org/wiki/Moore_matrix

Quelle est la complexité du calcul du déterminant d'une matrice de Moore de rang complet modulo un entier? $n \times n$

Le déterminant de Moore peut-il être réduit de utilisant des techniques FFT à pour certains ? $O(n^{3})$ $O(n\log^{a}n)$ $a \in \mathbb{R}_{+} \cup \{0\}$

La complexité de Moore det modulo est-elle un entier et Vandermonde dét la même chose? La complexité du déterminant de Vandermonde est (Page 644 dans le Manuel de l'informatique théorique: algorithmes et complexité par Jan Leeuwen) $O(n\log^{2}n)$

Poste similaire à l'actuel: Module déterminant m

cc.complexity-theory algebraic-complexity T ....
la source

Le déterminant de Moore peut-il même être calculé en temps O (n ^ 3) (sur une RAM entière)?

Jeffε

@ Jɛ ﬀ E C'est pourquoi j'ai mentionné le module aléatoire .

N \in N

$N \in \mathbb{N}$

T ....

Soit dit en passant, et je suis juste curieux, existe-t-il des applications connues qui bénéficieraient d'un tel algorithme "ultra-rapide"?

Juan Bermejo Vega

@J ffE, savez-vous si le calcul d'une double exponentiation modulaire sur est dans BPP pour trivial ?. Parce que c'est un problème pour calculer les coefficients de la matrice.

ε

$\varepsilon$

N

$N$

N

$N$

Juan Bermejo Vega

Réponses:

En général, il existe un algorithme théorique pour trouver la décomposition LU d'une matrice arbitraire en utilisant l' algorithme Coppersmith – Winograd , qui donne alors évidemment le déterminant (en ajoutant le temps ). Il y a cependant un problème que l'algorithme Coppersmith – Winograd n'est pas considéré comme utilisable dans la pratique. Afaik, les gens utilisent principalement l' algorithme Strassen à temps . Est-ce que Boost UBLAS lu_factorize ne l' utilise pas? $O(n^{2.376})$ $O(n)$ $O(n^{2.807})$

Dans votre cas, la matrice de Moore devrait admettre des optimisations considérables car, fondamentalement, toute procédure d'élimination gaussienne comme la décomposition LU peut être effectuée de manière abstraite. En effet, vous trouverez une belle formule pour calculer le déterminant de Moore référencé par wikipedia , ce que l'on prouve probablement en élaborant simplement la décomposition LU en général. $O(n)$

Jeff Burdges
la source

Salut Jeff: Quelle référence faites-vous référence pour la formule O (n ^ 2). Je pense que Vandermonde det peut être calculé en O (nlogn) mais je ne trouve pas de référence. Donc, Moore det devrait-il aussi être en O (nlogn)?

T ....

Oui, j'aurais dû dire O (n) évidemment, vraiment O (n log n) pour grand n.

Jeff Burdges

Salut Jeff: Avez-vous une référence?

T ....

@JeffBurdges: Si le temps d'exécution est O (n log n) "pour grand n", alors par définition, le temps d'exécution est O (n log n), pas O (n).

Jeffε

Je ne vois pas de formule référencée par Wikipedia. Au mieux, il ressemble à .

O (n)

$O(n)$

Θ (n^{2})

$\Theta(n^2)$

Peter Taylor

Il est important que, dans la définition que vous fournissez, la matrice vive dans un champ fini, disons où est premier. Cela vous permet d'utiliser le théorème d' Euler pour calculer les doubles exponentielles qui apparaissent dans la matrice au temps . Sinon, il semble même difficile de calculer les coefficients de la matrice sans factoriser . $\mathbb{Z}_m$ $m$ $a^{q^e}\mod m$ $O(\log (mn) \; M(\log m))$

a^{q^{i}} \equiv a^{q^{i} (\mod φ (m))} (\mod m)

$a^{q^i}\equiv a^{q^i\pmod{\varphi(m)}}\pmod m$

m

$m$

Si est premier ou peut être factorisé efficacement, la complexité la plus défavorable est dominée par le nombre d'étapes dont vous avez besoin pour la multiplication matricielle . Par exemple, l' approche de la forme normale de Smith que j'ai mentionnée dans la publication partenaire calculerait le déterminant dans le temps si vous utilisez "slow" algorithmes de multiplication . peut être choisi pour 2.373. $m$ $O(n^\omega)$ $O\left( n^\omega \; \log^2m\; \log (mn) \right)$ $^*$ $\omega$

Vous obtenez un ralentissement dans Moore vs Vandermonde car vous devez double-exponentier les coefficients de la matrice. Lorsque vous pouvez factoriser ce ralentissement est simplement polylogarithmique sur . Sinon, l' algorithme présenté vous donne une réduction de Cook à Double-Modular-Exponentiation sur . $m$ $m$ $\mathbb{Z}_m$

Remarque *: des algorithmes plus rapides pour la multiplication d'entiers vous permettent de remplacer par . $\log^2 m$ $M(\log m \log\log m)$

Mise à jour : sur la possibilité de réaliser . $O(n\log^a n)$

Je n'ai pas de réponse définitive à cela, mais j'ai trouvé des informations qui pourraient resserrer votre recherche.

Les algorithmes pour les matrices structurées qui calculent des quantités comme des déterminants dans le temps sont appelés "ultra-rapides" dans la littérature. Tous les algorithmes "ultra-rapides" connus pour les matrices structurées (Vandermonde, Toeplitz, Hankel) semblent s'appuyer sur une propriété commune de ces matrices connue sous le nom de "rang de déplacement" bas. Conférer la discussion sur le premier chapitre de ce livre (pages en accès libre), ou dans cet article [ACM] , [PDF] . $O(n\log^a n)$

D'après ce que j'ai lu, étant donné une matrice Moore , si vous pouviez trouver des matrices , telles que la nouvelle matrice (ou alternativement ) a la structure suivante $m\times n$ $M$ $A$ $B$ $L(M)=AM-MB$ $L(M)=M- AMB$

L (M) = \sum_{k = 1}^{r} g_{k} h_{k}^{T}

$L(M) = \sum_{k=1}^r g_k h_k^T$

, et le rang est petit (soit constant soit délimité par ), alors vous pouvez appliquer les techniques existantes (consultez le chapitre 5 du livre, ouvrez- pages d'accès) pour triangulariser et, par conséquent, calculer , en utilisant . Au-dessus, les , désignent des vecteurs. Si vous ne trouvez pas le livre ci-dessus pour lire le tout, cet article contient également de nombreuses informations sur ces méthodes. $r>0$ $o(\text{min} \;\{m,n\})$ $M$ $\det{M}$ $O(n\log^2 n)$ $g_k$ $h_k$

Malheureusement, je n'ai pas été en mesure de trouver une structure de rang à faible déplacement pour la matrice de Moore (Vandermonde l'a). La principale complication semble ici venir de la nature "non linéaire" de la double exponentielle. Si cela aide, les cas de Vandermonde, Cauchy, Toeplitz, Hankel sont traités dans le livre.

Juan Bermejo Vega
la source

Je peux faire vivre ma matrice dans un champ de caractère . Cependant, la taille des alphabets pour mon application prévue sera grande. Donc est de la forme pour un assez grand .

3

$3$

m

$m$

3^{k}

$3^{k}$

k

$k$

T ....

C'est très bien, puisque vous pouvez calculer la fonction totiente de :)

3^{k}

$3^k$

Juan Bermejo Vega

eh bien ça ne simplifie pas la complexité, je dirais puisque le champ est très très grand.

T ....

Cela simplifie les problèmes que je mentionne avec la double exponentiation. Puisque , vous pouvez utiliser le théorème d'Euler pour doubler l'exponentiation d' : tout d'abord, calculez , puis . Vous pouvez le faire dans le temps . En utilisant l'algorithme de multiplication des écoles, , et vous obtiendriez un coût "net" final de ce qui est efficace.

φ (3^{k}) = 3^{k} - 3^{k - 1}

$\varphi(3^k)=3^k-3^{k-1}$

a^{q^{i}} \mod m

$a^{q^i}\mod m$

b = q^{i} \mod φ (3^{k})

$b=q^i\mod \varphi(3^k)$

a^{b} \mod 3^{k}

$a^b\mod 3^k$

O (\log (n 3^{k}) M (k \log 3))

$O(\log(n3^k)M(k \log3))$

M (n) = n^{2}

$M(n)=n^2$

O (n^{ω} k^{2} l o g^{2} 3 (\log n + k \log 3))

$O(n^\omega k^2 log^2 3 (\log n + k\log 3))$

Juan Bermejo Vega

Peut-on remplacer par ? C'est l'économie que je veux savoir (peut être possible à partir de la structure matricielle). Avec , je ne gagne rien à mes fins.

ω

$\omega$

1 + ϵ

$1 + \epsilon$

ω \geq 2

$\omega \ge 2$

T ....