grand problème d'affectation dense de bas rang

9

maxπiAπi,iπ1:n

Ici est une matrice de bas rang . Les tailles typiques seraient (peut-être beaucoup plus grandes), .An×nrn=10000  r=15

Arnold Neumaier
la source
1
Par vous voulez dire le produit afin que vous parcouriez la matrice pour différents ? πiπ
Bill Barth
π parcourt toutes les permutations.
Arnold Neumaier
Cela ne devrait-il pas être alors? Aπ(i),i
Jack Poulson
@JackPoulson: et sont deux notations différentes pour l'image de sous la permutation . \i(i)πiiπ
Arnold Neumaier
Question interessante! Cherchez-vous à exploiter la structure de bas rang uniquement pour des raisons de stockage , c'est-à-dire pour éviter d'avoir à former la matrice entière lors de l'application d'un algorithme d'affectation traditionnel? Ou cherchez-vous un moyen d'exploiter le bas rang pour accélérer la recherche?
Michael Grant

Réponses:

3

Puisque avec , nous avons où est la matrice de permutation correspondant à .A=R1R2TR1,R2Rn×r

iAπi,i=i(PπA)i,i=trace(PπR1R2T)
Pππ

Pour tout , la trace peut être calculée comme (Cette quantité est également connue sous le nom de produit Frobenius , ).π

trace(PπR1R2T)=ik(PπR1)i,k(R2T)k,i=i,k((PπR1)R2)i,k.
PπR1:R2

Cette idée ne supprime pas le fardeau d'avoir à passer par toutes les permutations et la recherche de la force brute pour le maximum de tous les produits Frobenius, et en fait est a la même complexité arithmétique de calcul explicite . Cependant, il a beaucoup plus faibles besoins en mémoire puisque vous ne devez former réellement .A=R1R2TA

Nico Schlömer
la source