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}(n2) \) 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 (kleiner 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. Die Operatiom $a^q \Mod{p}$ wird als diskrete Exponentialfunktion (auch modulare Exponentiation oder modulares Potenzieren) bezeichnet. Die naive Berechnung, bestimme […]

Numerik

Mehrgitterverfahren

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 Mehrgittermethoden ihre guten Konvergenzeigenschaften auch für sehr feine Gitter […]