{"id":862,"date":"2014-01-06T12:00:12","date_gmt":"2014-01-06T17:00:12","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=862"},"modified":"2013-12-29T15:50:36","modified_gmt":"2013-12-29T20:50:36","slug":"the-rosser-matrix","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2014\/01\/06\/the-rosser-matrix\/","title":{"rendered":"The Rosser Matrix"},"content":{"rendered":"\r\n<div class=\"content\"><!--introduction--><p>The Rosser matrix is a classic matrix eigenvalue test problem.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#4c651ced-62b7-4892-9bfa-d32a51015947\">The Rosser function<\/a><\/li><li><a href=\"#f060fa2e-5362-4776-b251-ad299c73a317\">The eigenvalues<\/a><\/li><li><a href=\"#a3cc4e88-d49c-4c82-84d4-91bca1141970\">Exact solution<\/a><\/li><li><a href=\"#08877d24-88ac-44b5-a61f-5086ed7b1065\">J. Barkley Rosser<\/a><\/li><\/ul><\/div><h4>The Rosser function<a name=\"4c651ced-62b7-4892-9bfa-d32a51015947\"><\/a><\/h4><p>You may not have noticed the <tt>rosser<\/tt> function, although it has been on your path for as long as you have had MATLAB.<\/p><pre class=\"codeinput\">  which <span class=\"string\">rosser<\/span>\r\n<\/pre><pre class=\"codeoutput\">C:\\Program Files\\MATLAB\\R2014a\\toolbox\\matlab\\elmat\\rosser.m\r\n<\/pre><p>Here is the Rosser matrix.<\/p><pre class=\"codeinput\">  R = rosser\r\n<\/pre><pre class=\"codeoutput\">\r\nR =\r\n\r\n   611   196  -192   407    -8   -52   -49    29\r\n   196   899   113  -192   -71   -43    -8   -44\r\n  -192   113   899   196    61    49     8    52\r\n   407  -192   196   611     8    44    59   -23\r\n    -8   -71    61     8   411  -599   208   208\r\n   -52   -43    49    44  -599   411   208   208\r\n   -49    -8     8    59   208   208    99  -911\r\n    29   -44    52   -23   208   208  -911    99\r\n\r\n<\/pre><p>Here is most of the <tt>help<\/tt> entry.<\/p><pre>rosser Classic symmetric eigenvalue test problem.\r\n  This matrix was a challenge for many matrix eigenvalue algorithms.\r\n  But LAPACK's DSYEV routine used in MATLAB has no trouble with it.\r\n  The matrix is 8-by-8 with integer elements.\r\n  It has:\r\n      * A double eigenvalue.\r\n      * Three nearly equal eigenvalues.\r\n      * Dominant eigenvalues of opposite sign.\r\n      * A zero eigenvalue.\r\n      * A small, nonzero eigenvalue.<\/pre><h4>The eigenvalues<a name=\"f060fa2e-5362-4776-b251-ad299c73a317\"><\/a><\/h4><p>Here are the eigenvalues.<\/p><pre class=\"codeinput\">  format <span class=\"string\">long<\/span>\r\n  e = eig(R)\r\n<\/pre><pre class=\"codeoutput\">\r\ne =\r\n\r\n   1.0e+03 *\r\n\r\n  -1.020049018429998\r\n   0.000000000000000\r\n   0.000098048640722\r\n   1.000000000000000\r\n   1.000000000000000\r\n   1.019901951359278\r\n   1.020000000000000\r\n   1.020049018429997\r\n\r\n<\/pre><p>As the <tt>help<\/tt> entry says, there is a double eigenvalue at 1000; there are three nearly equal eigenvalues around 1020; the largest positive eigenvalue is matched in magnitude by the largest negative eigenvalue; there is an exact zero eigenvalue; and there is one relatively small eigenvalue near .098.<\/p><p>When I was a student fifty years ago just learning about matrix computation, there were several competing methods for matrix eigenvalue computation.  Francis and Wilkinson were just publishing their work on the QR algorithm, and EISPACK and MATLAB were years in the future.  So the Rosser matrix represented a serious test of the methods we had available at the time.  I have always admired the fact that Rosser had constructed one elegant matrix whose eigenvalue problem contained all of these challenges.<\/p><p>Today, the symmetric QR algorithm with Wilkinson's shift can easily handle the Rosser matrix.  But we still like to have it in our collection to use in testing other algorithms.<\/p><h4>Exact solution<a name=\"a3cc4e88-d49c-4c82-84d4-91bca1141970\"><\/a><\/h4><p>Using the Symbolic Toolbox, we can compute the exact eigenvalues. First, find the characteristic polynomial.<\/p><pre class=\"codeinput\">  p = poly2sym(charpoly(R),<span class=\"string\">'x'<\/span>)\r\n<\/pre><pre class=\"codeoutput\"> \r\np =\r\n \r\nx^8 - 4040*x^7 + 5080000*x^6 + 82518000*x^5 - 5327676250000*x^4 + 4287904631000000*x^3 - 1082852512000000000*x^2 + 106131000000000000*x\r\n \r\n<\/pre><p>The matrix is singular, so the constant term is zero.  The polynomial has degree eight, but it factors nicely into linear and quadratic factors.<\/p><pre class=\"codeinput\">  f = factor(p)\r\n<\/pre><pre class=\"codeoutput\"> \r\nf =\r\n \r\nx*(x - 1020)*(x^2 - 1040500)*(x^2 - 1020*x + 100)*(x - 1000)^2\r\n \r\n<\/pre><p>These low degree factors make it possible to obtain exact symbolic expressions for the eigenvalues.<\/p><pre class=\"codeinput\">  e = solve(f)\r\n<\/pre><pre class=\"codeoutput\"> \r\ne =\r\n \r\n                  0\r\n               1000\r\n               1020\r\n               1000\r\n     10*10405^(1\/2)\r\n    -10*10405^(1\/2)\r\n 100*26^(1\/2) + 510\r\n 510 - 100*26^(1\/2)\r\n \r\n<\/pre><p>However, these symbolic expressions do not immediately reveal the numerical properties that interest us.<\/p><h4>J. Barkley Rosser<a name=\"08877d24-88ac-44b5-a61f-5086ed7b1065\"><\/a><\/h4><p>J. Barkley Rosser, Sr., was a colleague of my mentors George Forsythe and John Todd at the Institute for Numerical Analysis at UCLA in the 1950s. He is the most prominent figure in the front row of this photo of the INA members that I use near the beginning of my talk about \"The Evolution of MATLAB\".  Forsythe is in the center of the group and Todd is in the back row, looking over Forsythe's shoulder.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/ina.jpg\" alt=\"\"> <\/p><p>Rosser spent much of his career as director of the famous Army Mathematics Research Center at the University of Wisconsin in Madison.  He is best known for his work in number theory and logic.  In 1936, he developed a version of Godel's incompleteness theorem that is now referred to as <i>Rosser's trick<\/i>.  Stated informally, it says \"For every proof of a theorem, there is a shorter proof of its negation.\".<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_98080996cb9345b2842ecdbcc5bcdc9f() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='98080996cb9345b2842ecdbcc5bcdc9f ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 98080996cb9345b2842ecdbcc5bcdc9f';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2013 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_98080996cb9345b2842ecdbcc5bcdc9f()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2014a<br><\/p><p class=\"footer\"><br>\r\n      Published with MATLAB&reg; R2014a<br><\/p><\/div><!--\r\n98080996cb9345b2842ecdbcc5bcdc9f ##### SOURCE BEGIN #####\r\n%% The Rosser Matrix\r\n% The Rosser matrix is a classic matrix eigenvalue test problem.\r\n\r\n%% The Rosser function\r\n% You may not have noticed the |rosser| function, although it has been on\r\n% your path for as long as you have had MATLAB.\r\n%\r\n\r\n  which rosser \r\n\r\n%%\r\n% Here is the Rosser matrix.\r\n\r\n  R = rosser\r\n\r\n%%\r\n% Here is most of the |help| entry. \r\n%\r\n%  rosser Classic symmetric eigenvalue test problem.\r\n%    This matrix was a challenge for many matrix eigenvalue algorithms.\r\n%    But LAPACK's DSYEV routine used in MATLAB has no trouble with it.\r\n%    The matrix is 8-by-8 with integer elements.\r\n%    It has:\r\n%        * A double eigenvalue.\r\n%        * Three nearly equal eigenvalues.\r\n%        * Dominant eigenvalues of opposite sign.\r\n%        * A zero eigenvalue.\r\n%        * A small, nonzero eigenvalue.\r\n\r\n%% The eigenvalues\r\n% Here are the eigenvalues.\r\n\r\n  format long\r\n  e = eig(R)\r\n\r\n%%\r\n% As the |help| entry says, there is a double eigenvalue at 1000;\r\n% there are three nearly equal eigenvalues around 1020; the largest positive\r\n% eigenvalue is matched in magnitude by the largest negative eigenvalue;\r\n% there is an exact zero eigenvalue; and there is one relatively small\r\n% eigenvalue near .098.\r\n\r\n%%\r\n% When I was a student fifty years ago just learning about matrix\r\n% computation, there were several competing methods for matrix eigenvalue\r\n% computation.  Francis and Wilkinson were just publishing their work on\r\n% the QR algorithm, and EISPACK and MATLAB were years in the future.  So the\r\n% Rosser matrix represented a serious test of the methods we had available\r\n% at the time.  I have always admired the fact that Rosser had constructed\r\n% one elegant matrix whose eigenvalue problem contained all of these\r\n% challenges.\r\n\r\n%%\r\n% Today, the symmetric QR algorithm with Wilkinson's shift can easily handle\r\n% the Rosser matrix.  But we still like to have it in our collection to\r\n% use in testing other algorithms.\r\n\r\n%% Exact solution\r\n% Using the Symbolic Toolbox, we can compute the exact eigenvalues.\r\n% First, find the characteristic polynomial.\r\n\r\n  p = poly2sym(charpoly(R),'x') \r\n\r\n%% \r\n% The matrix is singular, so the constant term is zero.  The polynomial has\r\n% degree eight, but it factors nicely into linear and quadratic factors.\r\n\r\n  f = factor(p)\r\n\r\n%%\r\n% These low degree factors make it possible to obtain exact symbolic\r\n% expressions for the eigenvalues.\r\n\r\n  e = solve(f)\r\n\r\n%% \r\n% However, these symbolic expressions do not immediately reveal the numerical\r\n% properties that interest us.\r\n\r\n%% J. Barkley Rosser\r\n% J. Barkley Rosser, Sr., was a colleague of my mentors George Forsythe and\r\n% John Todd at the Institute for Numerical Analysis at UCLA in the 1950s.\r\n% He is the most prominent figure in the front row of this photo of the INA\r\n% members that I use near the beginning of my talk about \"The Evolution of\r\n% MATLAB\".  Forsythe is in the center of the group and Todd is in the back\r\n% row, looking over Forsythe's shoulder.\r\n%\r\n% <<ina.jpg>>\r\n%\r\n\r\n%%\r\n% Rosser spent much of his career as director of the famous Army Mathematics\r\n% Research Center at the University of Wisconsin in Madison.  He is best\r\n% known for his work in number theory and logic.  In 1936, he developed\r\n% a version of Godel's incompleteness theorem that is now referred to as\r\n% _Rosser's trick_.  Stated informally, it says \"For every proof of a\r\n% theorem, there is a shorter proof of its negation.\".\r\n\r\n##### SOURCE END ##### 98080996cb9345b2842ecdbcc5bcdc9f\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/ina.jpg\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>The Rosser matrix is a classic matrix eigenvalue test problem.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2014\/01\/06\/the-rosser-matrix\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[13,4,6,8,20],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/862"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=862"}],"version-history":[{"count":11,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/862\/revisions"}],"predecessor-version":[{"id":871,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/862\/revisions\/871"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=862"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=862"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=862"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}