Finding number of saddle points of a matrix

Discussion of Common Lisp
Post Reply
wvxvw
Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

Finding number of saddle points of a matrix

Post by wvxvw » Tue Feb 21, 2012 5:12 am

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.

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

Re: Finding number of saddle points of a matrix

Post by ramarren » Tue Feb 21, 2012 6:10 am

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

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

Re: Finding number of saddle points of a matrix

Post by wvxvw » Tue Feb 21, 2012 10:07 am

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 :)

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

Re: Finding number of saddle points of a matrix

Post by gugamilare » Tue Feb 21, 2012 9:09 pm

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. :)

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

Re: Finding number of saddle points of a matrix

Post by wvxvw » Sat Feb 25, 2012 3:28 am

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 :)

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

Re: Finding number of saddle points of a matrix

Post by gugamilare » Sat Feb 25, 2012 6:15 pm

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).

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

Re: Finding number of saddle points of a matrix

Post by wvxvw » Thu Mar 01, 2012 10:58 am

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

Post Reply