Iskanje sedla matrike

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.