Als Teil eines synthetischen Rauschgenerierungsalgorithmus muss ich viele große nicht-singuläre quadratische Matrizen im Handumdrehen konstruieren
a i, j (i, j: 1..n) / ∀ (i, j) a i, j und 0 i, j ≤ k und Det [a] ≠ 0
aber das a i, j sollte auch zufällig nach einer gleichmäßigen Verteilung in [0, k] sein.
In seiner gegenwärtigen Inkarnation hat das Problem n ≅ 300, k≅ 100.
In Mathematica kann ich sehr schnell Zufallselementmatrizen erzeugen, aber das Problem ist, dass ich auch auf Singularität prüfen muss. Ich verwende derzeit den Determinant-Wert dafür.
Das Problem ist, dass diese Prüfung für die 300x300-Matrizen etwas in der Nähe von 2 Sekunden dauert, und das kann ich mir nicht leisten.
Natürlich kann ich die Zeilen konstruieren, indem ich eine zufällige erste Zeile auswähle und dann aufeinanderfolgende orthogonale Zeilen konstruiere, aber ich bin mir nicht sicher, wie man garantieren kann, dass diese Zeilen ihre Elemente einer gleichmäßigen Verteilung in [0, k] folgen lassen.
Ich suche nach einer Lösung in Mathematica, aber auch ein schnellerer Algorithmus zur Erzeugung der Matrizen ist willkommen.
NB & gt; Die Bedingung U [0, k] bedeutet, dass eine Menge von Matrizen genommen wurde, jede Position (i, j) über die Menge sollte einer gleichmäßigen Verteilung folgen.
Wenn Sie in den Singularitätstests numerische Näherungsmatrizen verwenden, erhalten Sie eine viel bessere Geschwindigkeit.
%Vor%Aus [57] = {6.8640000, False}
%Vor%Out [58] = {0.0230000, False}
%Vor%Aus [59] = {0.1710000, False}
Leider ist dieser schnellste Test nicht zuverlässig. Aber der Rang-Test sollte gut funktionieren. Hier ist ein schnelles Beispiel, in dem wir die letzte Zeile durch die Summe der vorherigen Zeilen ersetzen.
%Vor%Aus [70] = {9.4750000, True}
%Vor%Out [69] = {0.0470000, False}
%Vor%Out [71] = {0.1440000, True}
Im Prinzip nehme ich an, dass es eine geringe Chance gibt, dass der Rang-Test ein falsches Negativ geben könnte, sagen wir aufgrund schlechter Konditionierung. Da Ihre Verwendung False Positives (dh inkorrekte Behauptungen der Singularität) besser tolerieren wird, könnten Sie stattdessen die Singularität über einen Primzahlmodul testen. Ich denke, das war eine der Empfehlungen, die andere gemacht haben.
Fortsetzung der obigen Beispiele:
%Vor%Aus [77] = {0.6320000, 4054}
%Vor%Aus [78] = {0.6470000, 0}
Das ist langsam, aber schneller als über die Rationalen zu arbeiten. Für das, was es wert ist, bin ich bei den meisten Anwendungen ziemlich zuversichtlich in den Ergebnissen des schnelleren Testens über MatrixRank [N [Matrix]].
Daniel Lichtblau Wolfram Forschung
Sowohl in Matlab als auch in Octave sind die Determinante und die LU-Faktorisierung einer 500x500-Matrix im Grunde augenblicklich. Hat Mathematica einen Modus, in dem es LAPACK oder eine ähnliche Bibliothek aufrufen kann? Möglicherweise müssen Sie annotieren, dass Ihre Arrays als Fließkommazahlen und nicht symbolisch behandelt werden sollten. das könnte es viel schneller machen. Als Vergleichspunkt benötigt LU auf einer 5000x5000-Matrix mit Octave 8,66 Sekunden auf meinem System; 500x500 sollte etwa 1000 mal schneller sein als das.
Hier ist eine Erweiterung eines Kommentars, den ich ein bisschen gemacht habe. Ich stimme Dan zu, dass es höchst unwahrscheinlich ist, dass die numerische Version ein falsch positives Ergebnis liefert. Sie können dieses Szenario jedoch vermeiden, indem Sie die Singulärwerte überprüfen und False zuverlässig zurückgeben, wenn der kleinste Singulärwert größer als eine Fehlertoleranz ist. (Zugegeben, es könnte ein bisschen schwierig sein, eine beweisbare Toleranz zu finden.) Wenn der kleinste singuläre Wert unbequem klein ist, können Sie Det auf die ganze Matrix anwenden.
Hier ist eine Funktion, die für die meisten nicht singulären Matrizen schnell False zurückgeben sollte. Wenn die Matrix nahe bei singular ist, wird eine teurere ganzzahlige Berechnung durchgeführt.
%Vor%Hier sind 200 Matrizen, die Ihrer Beschreibung entsprechen. Einer in der Mitte wurde so eingerichtet, dass er einzigartig ist.
%Vor%Lasst uns nun die Indizes aller einzelnen Matrizen finden und dabei zusehen, wie wir vorgehen.
%Vor%Tags und Links algorithm math random wolfram-mathematica