## Finding number of saddle points of a matrix

Discussion of Common Lisp

### Finding number of saddle points of a matrix

Hi, I've encountered this question, and I thought it would be interesting to try to solve it with the least complexity. So far I only have a fair naive solution with the complexity being O(2 * x * y), but it looks like it should be possible to reduce it - yet I cannot find a good way to do it.

Code: Select all
`(defun saddle-points-naive (matrix)  (let* ((x (array-dimension matrix 0))    (y (array-dimension matrix 1))    (mins (make-array x))    (maxs (make-array y))    (element)    (total 0))    (dotimes (i x)      (dotimes (j y)   (setf element (aref matrix i j)         (aref maxs j)         (if (zerop i)        element        (max element (aref maxs j)))         (aref mins i)         (if (zerop j)        element        (min element (aref mins i))))))    (dotimes (i x total)      (dotimes (j y)   (when (= (aref maxs i)       (aref mins j)       (aref matrix i j))     (incf total))))))(defparameter *random-matrix*  (let ((m (make-array '(5 5))))    (dotimes (z 25 m)      (setf (aref m (floor (/ z 5)) (mod z 5))       (random 25)))))(defparameter *flat-matrix*  (make-array '(3 3) :initial-element 1))(defparameter *parabolic-matrix*  (make-array '(5 5)         :initial-contents         '((5 3 0 3 5)      (7 5 3 5 7)      (9 7 5 7 9)      (7 5 3 5 7)      (5 3 0 3 5))))(saddle-points-naive *random-matrix*)(saddle-points-naive *flat-matrix*)(saddle-points-naive *parabolic-matrix*)`

For the reference, saddle point is a value in the matrix, which is at the same time the smallest value in its row and the greatest value in it's column.
wvxvw

Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

### Re: Finding number of saddle points of a matrix

See this Stack Overflow question. The complexity cannot be lower than O(xy) because you have to touch every point of the matrix.
ramarren

Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

### Re: Finding number of saddle points of a matrix

Well, even though O(xy) would be formally the same as O(2xy) (2 being a factor of the operation cost), I still think there must be a better way to do it because you could cancel certain possibilities while searching for minimum and maximum of the row/column. Or, maybe there could've been some sort of opportunistic algorithm, that would assume that the point is a saddle point and verify that, canceling those it finds on the way as not suitable. Or, maybe it cold've been possible by building a tree from the matrix and somehow collapsing the branches if they are found to be "bad".

I'm thinking about this more in terms of database query (possible) optimization, where multiple conditions should be applied to the same entry, but only certain combination of all conditions yields the desired result (so it's not necessary a 2D matrix). Maybe, even if there is a probabilistic, but significantly faster approach, I'd like to find that wvxvw

Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

### Re: Finding number of saddle points of a matrix

Divide and conquer Divide the matrix in 4 (cut in half both horizontally and vertically), then (recursively) find the saddle points in the submatrix. Then, any possible saddle point of the matrix must be one of the saddle points of the submatrix.

For instance, to test if a saddle point of the upper-left submatrix is a saddle, you only have to test if it is greater then the elements of the same column in the lower-half submatrix. If one of those elements is a saddle point, better still, just check if the former is greater than the latter and you are done. gugamilare

Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

### Re: Finding number of saddle points of a matrix

Sorry, took me some time to reply. Well, the thing is, it's not sorting, so, we can't discard the branches (your idea is similar to quicksort - am I naming it correctly? The algorithm, where you take half of an array, and then half of the half and so on?).

But trying to do it myself I didn't see any special good probabilistic way, then simply selecting coordinates at random, so, nothing "tricky" so far wvxvw

Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

### Re: Finding number of saddle points of a matrix

You got it backwards. First you compute the saddle points of the submatrix, only then you use that information to compute the saddle points of the whole matrix.

It's more like merge sort than like quicksort. It's divide and conquer (merge sort), not conquer and divide (quicksort).
gugamilare

Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

### Re: Finding number of saddle points of a matrix

Ah... I think I'm starting to understand, I'll try to write the code for it, and we'll see wvxvw

Posts: 127
Joined: Sat Mar 26, 2011 6:23 am 