{"action":"opened","issue":{"url":"https://api.github.com/repos/mshabunin/test2/issues/1169","labels_url":"https://api.github.com/repos/mshabunin/test2/issues/1169/labels{/name}","comments_url":"https://api.github.com/repos/mshabunin/test2/issues/1169/comments","events_url":"https://api.github.com/repos/mshabunin/test2/issues/1169/events","html_url":"https://github.com/mshabunin/test2/issues/1169","id":96110948,"number":1169,"title":"SVD in Lapack is suboptimal, by means of Givens rotations vs. Hauseholder mirroring","user":{"login":"opencv-pushbot","id":2051563,"avatar_url":"https://avatars.githubusercontent.com/u/2051563?v=3","gravatar_id":"","url":"https://api.github.com/users/opencv-pushbot","html_url":"https://github.com/opencv-pushbot","followers_url":"https://api.github.com/users/opencv-pushbot/followers","following_url":"https://api.github.com/users/opencv-pushbot/following{/other_user}","gists_url":"https://api.github.com/users/opencv-pushbot/gists{/gist_id}","starred_url":"https://api.github.com/users/opencv-pushbot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/opencv-pushbot/subscriptions","organizations_url":"https://api.github.com/users/opencv-pushbot/orgs","repos_url":"https://api.github.com/users/opencv-pushbot/repos","events_url":"https://api.github.com/users/opencv-pushbot/events{/privacy}","received_events_url":"https://api.github.com/users/opencv-pushbot/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-07-20T17:05:13Z","updated_at":"2015-07-20T17:05:13Z","closed_at":null,"body":"Transferred from http://code.opencv.org/issues/3018\r\n```\n|| Zoltan Prohaszka on 2013-05-11 16:17\n|| Priority: Normal\n|| Affected: None\n|| Category: core\n|| Tracker: Feature\n|| Difficulty: None\n|| PR: \n|| Platform: None / None\n```\n\nSVD in Lapack is suboptimal, by means of Givens rotations vs. Hauseholder mirroring\n-----------\n```\nMost Multiple View Computer Vision Algorithms have to \r\nsolve overdetermined homogeneous linear equations, for \r\nwhich Singular Value Decomposition (SVD) is the proper method. \r\n\r\nThe SVD implementation given in Lapack achieves band diagonal shape \r\nby applying Givens rotations. Hausholder mirroring transformations \r\ncan zero a partial row for once, not only one element, thus there are \r\nfaster by a factor of n. (the smallest size of the input matrix)\r\n\r\nA typipical 3D reconstruction algorithm may spend many time by finding inliers\r\nof a proper motion stereo model by RANSAC. \r\nFor a not so easy image pair, RANSAC (inside findfundamental()) \r\nexecutes 8x8 SVD several hundred times. \r\n\r\nAn other example, the JAMA package of NIST uses Hauseholder transformations.\r\n(I attach a commented version of the algorithm, and the original \r\nfile also). The JAMA package have another attractive feature regarding \r\nthe eigenvalue-decomposition of non-symmetric matrices: It contains \r\nthe random step introduced by the MATLAB team to avoid the algorithm to stuck.\r\n(It can be tested by big permutation matrices). \r\n\r\nThe JAMA package comes with very liberate licence. \r\nIt has also disadvantages:\r\n-Most numerical loops are designed to work only with rectangular matrices of \r\none orientation ('landscape' or 'portrait'), so wrapper routines would be needed\r\nfor universal functionality. \r\n-It is not implemented to take advantage of SIMD or multithreaded execution. \r\n-It contains some calculations which give numeric stability very near to \r\nthe margin of floating numeric represantations, but results slower execution \r\nin other, common cases (hypot and division instead of multiplication by reciprocal). \r\nI did not analize how unsafe the faster versions would be, so I did not modify these\r\nfor my versions.\r\n\r\nI would like to ask for the opinion of the community, how the better functionality\r\nshould be incorporated in openCV. \r\n\r\nRegards:\r\nzol\r\n\r\nI set the priority normal because SVD is executed frequently. Otherwise I would give Low.\n```\n\nHistory\n-------"}}