Saddle point detection algorithms in matrices

Danevska, Ana (author), 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.

• Language: English
• Keywords: saddle points, matrices, linear algebra, optimization techniques, algorithm
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2024
• PID: 20.500.12556/RUL-162179
• Publication date in RUL: 19.09.2024

Secondary language

• Language: Slovenian
• Title: Iskanje sedla matrike

Abstract

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.

• Keywords: sedlo, matrike, optimizacijske tehnike, algoritem