Saddle point detection algorithms in matrices

Danevska, Ana (avtor), Hočevar, Tomaž (mentor)

This diploma thesis addresses the problem of finding saddle points in matrices, a critical concept in various applications of linear algebra and optimization techniques. The thesis begins with the mathematical definition of saddle points, followed by a comprehensive review of existing methods for their detection, including the algorithms proposed by Donald Knuth and more recent advancements. A significant focus is given to the analysis of the article "Finding a Saddle Point Faster than Sorting", which presents a crucial improvement in the time complexity of saddle point detection. The article introduces a new algorithm with a complexity of $O(n \log^* n) \subset o(n \log n)$, representing a substantial advancement over previous methods. Experimental analysis on various matrix types demonstrates that this new approach enables faster and more efficient detection of saddle points with reduced computational requirements.

• Jezik: Angleški jezik
• Ključne besede: saddle points, matrices, linear algebra, optimization techniques, algorithm
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2024
• PID: 20.500.12556/RUL-162179
• Datum objave v RUL: 19.09.2024

Sekundarni jezik

• Jezik: Slovenski jezik
• Naslov: Iskanje sedla matrike

Izvleček

Diplomska naloga obravnava problem iskanja sedla v matrikah, ki so ključne v različnih aplikacijah linearne algebre in optimizacijskih tehnik. V nalogi je najprej predstavljena matematična definicija sedlastih točk, nato pa sledi podroben pregled obstoječih metod za njihovo iskanje, vključno z algoritmi Donalda Knutha ter novejšimi izboljšavami. Poseben poudarek je namenjen analizi članka "Finding a Saddle Point Faster than Sorting", ki predstavlja pomemben napredek v časovni kompleksnosti iskanja sedlastih točk. Članek uvaja nov algoritem s kompleksnostjo $O(n \log^* n) \subset o(n \log n)$, kar je bistveno izboljšanje v primerjavi z dosedanjimi metodami. Eksperimentalna analiza preučevanih algoritmov na različnih vrstah matrik je pokazala, da nov pristop omogoča hitrejše in učinkovitejše iskanje sedla z nižjimi računskimi zahtevami.

• Ključne besede: sedlo, matrike, optimizacijske tehnike, algoritem