Page 1 of 1

Finding number of saddle points of a matrix

Posted: Tue Feb 21, 2012 5:12 am
by wvxvw
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.

Re: Finding number of saddle points of a matrix

Posted: Tue Feb 21, 2012 6:10 am
by ramarren
See this Stack Overflow question. The complexity cannot be lower than O(xy) because you have to touch every point of the matrix.

Re: Finding number of saddle points of a matrix

Posted: Tue Feb 21, 2012 10:07 am
by wvxvw
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 :)

Re: Finding number of saddle points of a matrix

Posted: Tue Feb 21, 2012 9:09 pm
by gugamilare
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. :)

Re: Finding number of saddle points of a matrix

Posted: Sat Feb 25, 2012 3:28 am
by wvxvw
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 :)

Re: Finding number of saddle points of a matrix

Posted: Sat Feb 25, 2012 6:15 pm
by gugamilare
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).

Re: Finding number of saddle points of a matrix

Posted: Thu Mar 01, 2012 10:58 am
by wvxvw
Ah... I think I'm starting to understand, I'll try to write the code for it, and we'll see :)