Saddle point detection algorithms in matricesDanevska, Ana (Avtor) Hočevar, Tomaž (Mentor) saddle pointsmatriceslinear algebraoptimization techniquesalgorithmThis 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.20242024-09-19 12:20:01Diplomsko delo/naloga162179sl