Schlagwort: schnelle Algorithmen

Die Wahl des passenden Algorithmus ist entscheidend für die Effizienz einer Lösung. Schnelle Algorithmen lösen Probleme im Vergleich zu traditionellen Methoden mit deutlich höherer Geschwindigkeit und/oder geringerem Speicherplatzbedarf. Dies resultiert oft aus einer besseren Komplexitätsklasse, was bedeutet, dass der Rechenaufwand deutlich reduziert wird. Ein Beispiel dafür ist die schnelle Fourier-Transformation (FFT), die im Vergleich zur direkten Auswertung der trigonometrischen Summenformel eine erhebliche Zeitersparnis bietet (Komplexität \( \mathcal{O}(n^2) \) vs. \(\mathcal{O}(n \log n) )\). Auch das Modulare Potenzieren zeigt, wie die Wahl des Verfahrens die Laufzeit von Sekunden auf wenige Mikrosekunden reduzieren kann.

Mathematische Modelle, Numerik

Radiosity equation

\( \def\x{{\bf x}} \def\y{{\bf y}} \def\out{{\rm out}} \newcommand{\Spro}[2]{\langle {#1},{#2} \rangle} \) Die radiosity equation ist eine Integralgleichung, die den Strahlungs- bzw. Energieaustausch zwischen diffusen grauen Oberflächen modelliert. Sie lautet \begin{equation} \label{IGLqout2} q_\out (\x) = \epsilon \, \sigma \, T^4(\x) + \rho \, \int_\Gamma k(\x,\y) \, q_\out (\y) \, d\y, \end{equation} […]

Programmierung

Modulares Potenzieren

\(\newcommand{\Mod}[1]{\ \mathrm{mod}\ #1}\) Für einen Primzahltest, basierend auf den kleinen Fermatscher Satz, wird die Auswertung von $$ a^{p-1} \Mod{p}, \qquad 0 < a < p , \quad a,p \in \mathbb{N} $$ für große Zahlen $a$ und $p$ benötigt. Diese Operation nennt man diskrete Exponentialfunktion oder modulare Exponentiation. Die naive Berechnung, […]

Numerik

Mehrgitterverfahren

\( \def\x{{\bf x}} \def\y{{\bf y}} \newcommand{\Spro}[2]{\langle {#1},{#2} \rangle} \) Mehrgitterverfahren sind in der Lage große Gleichungssysteme mit mehreren Millionen Unbekannten, die sich aus der Diskretisierung von physikalischen Simulationsmodellen ergeben und bestimmte Anforderungen erfüllen, schnell zu lösen. Im Gegensatz zu klassischen Iterationsverfahren, deren Konvergenzrate mit zunehmender Feinheit des Gitters abnimmt, behalten […]