{"id":9596,"date":"2023-01-10T16:45:12","date_gmt":"2023-01-10T21:45:12","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=9596"},"modified":"2023-01-18T10:02:56","modified_gmt":"2023-01-18T15:02:56","slug":"singular-matrix-pencils-and-the-qz-algorithm-update","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2023\/01\/10\/singular-matrix-pencils-and-the-qz-algorithm-update\/","title":{"rendered":"Singular Matrix Pencils and the QZ Algorithm, Update"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>(The January 5 posting was premature and incomplete.)<\/p><p>This year, 2023, is the 50-th anniversary of the QZ algorithm for the generalized matrix eigenvalue problem,<\/p><pre>  Ax = &#955;Bx<\/pre><p>The algorithm avoids inverting either <tt>A<\/tt> or <tt>B<\/tt>. And, importantly, the QZ algorithm can be used to detect and analyze exceptional instances of the problem known as <i>singular pencils<\/i>. These pencils do not occur in the standard eigenvalue problem where <tt>B<\/tt> is the identity matrix.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#59d30988-fe9f-4381-bf4b-70b9181f1d24\">Singular pencils<\/a><\/li><li><a href=\"#aa953fcf-a488-43bb-8976-bef668d4b373\">3-by-3 example<\/a><\/li><li><a href=\"#ebedf1c8-dc25-443b-9232-8e963a75eed3\">Wilkinson example<\/a><\/li><li><a href=\"#2c8b301b-125b-4389-a5ea-fd8eccc8d4ba\">References<\/a><\/li><\/ul><\/div><h4>Singular pencils<a name=\"59d30988-fe9f-4381-bf4b-70b9181f1d24\"><\/a><\/h4><p>A matrix pencil is <i>singular<\/i> if both <tt>A<\/tt> and <tt>B<\/tt> are singular and, moreover, <tt>A<\/tt> - &#955; <tt>B<\/tt> is singular for all &#955;.  Equivalently,<\/p><pre>  det(A - &#955;B) = 0 for all &#955;.<\/pre><p>Singular pencils are more insidious than might appear at first glance. In some sense, the spectrum is the entire complex plane.<\/p><p>There are no singular pencils with the standard eigenvalue problem<\/p><pre>  Ax = &#955;x<\/pre><p>where <tt>B<\/tt> is the identity matrix and certainly nonsingular.<\/p><p>If <tt>A<\/tt> and <tt>B<\/tt> are both real symmetric or complex Hermitian, but neither is positive definite, the pencil may or may not be singular. Symmetric problems occur frequently and there are separate algorithms and perturbation and convergence theories.<\/p><p>The QZ algorithm does not compute the eigenvalues &#955; until the very last step.  It stably reduces <tt>A<\/tt> and <tt>B<\/tt> to triangular form with diagonals &#945; and &#946;. The eigenvalues are then the ratios<\/p><pre>  &#955; = &#945;.\/&#946;<\/pre><p>Isolated zeros in &#945; or &#946; yield zero or infinite eigenvalues with no special difficulties.  Singular pencils occur if and only if zeros in &#945; and &#946; occur <i>with the same index<\/i> and (with exact arithmetic) lead to &#955; = 0\/0 = NaN.<\/p><p>With a singular pencil, some, perhaps all, of the diagonal values in &#945; and &#946; are highly sensitive to perturbation, and all of the eigenvalues computed from the ratios are suspect.  Theoretically the ill-conditioned eigenvalues can be determined from the Kronecker Canonical Form, a generalization of the notorious Jordan Canonical Form.  But, like the Jordan Form, the Kronecker Form cannot provide a stable numerical algorithm.<\/p><h4>3-by-3 example<a name=\"aa953fcf-a488-43bb-8976-bef668d4b373\"><\/a><\/h4><pre class=\"codeinput\">   A = [9 8 7; 6 5 4; 3 2 1]\r\n\r\n   B = [1 3 2; 4 6 5; 7 9 8]\r\n<\/pre><pre class=\"codeoutput\">\r\nA =\r\n\r\n     9     8     7\r\n     6     5     4\r\n     3     2     1\r\n\r\n\r\nB =\r\n\r\n     1     3     2\r\n     4     6     5\r\n     7     9     8\r\n\r\n<\/pre><p>Let's verify that this is a singular pencil. Use the Symbolic Math Toolbox to introduce a free variable.<\/p><pre class=\"codeinput\">   syms <span class=\"string\">lambda<\/span>\r\n   AB = A - lambda*B\r\n<\/pre><pre class=\"codeoutput\"> \r\nAB =\r\n \r\n[  9 - lambda, 8 - 3*lambda, 7 - 2*lambda]\r\n[6 - 4*lambda, 5 - 6*lambda, 4 - 5*lambda]\r\n[3 - 7*lambda, 2 - 9*lambda, 1 - 8*lambda]\r\n \r\n<\/pre><p>Without further computation, we can see that the second row is the average of the first and third rows for all <tt>lambda<\/tt> and consequently that the determinant must be identically zero.<\/p><p>With exact arithmetic, each of these statements would produce the same eigenvalues.  After the introduction of some roundoff error, two of the <tt>lambdas<\/tt> are indeterminant, but <tt>lambda = -1<\/tt> is present in all four results. Is <tt>lambda = -1<\/tt> a stable eigenvalue?<\/p><pre class=\"codeinput\">   lambda_AB = eig(A,B)\r\n   lambda_BA = 1.\/eig(B,A)\r\n   lambda_ATBT = eig(A',B')\r\n   lambda_BTAT = 1.\/eig(B',A')\r\n<\/pre><pre class=\"codeoutput\">\r\nlambda_AB =\r\n\r\n    1.8984\r\n   -1.0000\r\n   -0.0807\r\n\r\n\r\nlambda_BA =\r\n\r\n   -1.0000\r\n    0.5837\r\n   -0.9274\r\n\r\n\r\nlambda_ATBT =\r\n\r\n    0.0829\r\n       Inf\r\n   -1.0000\r\n\r\n\r\nlambda_BTAT =\r\n\r\n   -0.9661\r\n         0\r\n   -1.0000\r\n\r\n<\/pre><p>The triangular matrices for <tt>lambda_AB<\/tt>.<\/p><pre class=\"codeinput\">   [QAZ,QBZ] = qz(A,B);\r\n   QAZ\r\n   QBZ\r\n<\/pre><pre class=\"codeoutput\">\r\nQAZ =\r\n\r\n    1.6131   10.2664  -11.0905\r\n         0   -4.2969    5.9613\r\n         0         0   -0.0000\r\n\r\n\r\nQBZ =\r\n\r\n    0.7898    6.8901  -13.5242\r\n         0    4.2969   -5.9613\r\n         0         0    0.0000\r\n\r\n<\/pre><p>Careful examination of the diagonals reveals that <tt>alfa(2)\/beta(2)<\/tt> is producing the <tt>-1<\/tt>, while <tt>alfa(3)\/beta(3)<\/tt> is roundoff over roundoff.<\/p><pre class=\"codeinput\">   format <span class=\"string\">long<\/span> <span class=\"string\">e<\/span>\r\n   alfa = diag(QAZ)\r\n   beta = diag(QBZ)\r\n   format <span class=\"string\">short<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nalfa =\r\n\r\n     1.613087771308989e+00\r\n    -4.296911800112353e+00\r\n    -1.965207685813115e-15\r\n\r\n\r\nbeta =\r\n\r\n     7.898460671891234e-01\r\n     4.296911800112357e+00\r\n     1.359052275299816e-15\r\n\r\n<\/pre><h4>Wilkinson example<a name=\"ebedf1c8-dc25-443b-9232-8e963a75eed3\"><\/a><\/h4><p>Jim Wilkinson published a survey paper about QZ and Kronecker products in 1979.  One of his examples is<\/p><pre class=\"codeinput\">   A = [4 3 2 5; 6 4 2 7; -1 -1 -2 -2; 5 3 2 6]\r\n\r\n   B = [2 1 3 4; 3 3 3 5;  0  0 -3 -2; 3 1 3 5]\r\n<\/pre><pre class=\"codeoutput\">\r\nA =\r\n\r\n     4     3     2     5\r\n     6     4     2     7\r\n    -1    -1    -2    -2\r\n     5     3     2     6\r\n\r\n\r\nB =\r\n\r\n     2     1     3     4\r\n     3     3     3     5\r\n     0     0    -3    -2\r\n     3     1     3     5\r\n\r\n<\/pre><p>Use the Symbolic Math Toolbox to verify that this is a singular pencil.<\/p><pre class=\"codeinput\">   syms <span class=\"string\">lambda<\/span>\r\n   AB = A - lambda*B\r\n<\/pre><pre class=\"codeoutput\"> \r\nAB =\r\n \r\n[4 - 2*lambda,   3 - lambda, 2 - 3*lambda, 5 - 4*lambda]\r\n[6 - 3*lambda, 4 - 3*lambda, 2 - 3*lambda, 7 - 5*lambda]\r\n[          -1,           -1, 3*lambda - 2, 2*lambda - 2]\r\n[5 - 3*lambda,   3 - lambda, 2 - 3*lambda, 6 - 5*lambda]\r\n \r\n<\/pre><p>The determinant is identically zero for all <tt>lambda<\/tt>.<\/p><pre class=\"codeinput\">   d = det(AB)\r\n<\/pre><pre class=\"codeoutput\"> \r\nd =\r\n \r\n0\r\n \r\n<\/pre><p>With exact arithmetic, each of these statements would produce the same eigenvalues, but in practice each set is different. None of the eigenvalues is stable.<\/p><pre class=\"codeinput\">   lambda_AB = eig(A,B)\r\n   lambda_BA = 1.\/eig(B,A)\r\n   lambda_ATBT = eig(A',B')\r\n   lambda_BTAT = 1.\/eig(B',A')\r\n<\/pre><pre class=\"codeoutput\">\r\nlambda_AB =\r\n\r\n    1.2056\r\n    0.7055\r\n   -1.0000\r\n      -Inf\r\n\r\n\r\nlambda_BA =\r\n\r\n    1.5097\r\n    0.6408\r\n         0\r\n   -1.0000\r\n\r\n\r\nlambda_ATBT =\r\n\r\n  -0.2141 + 0.2033i\r\n  -0.2141 - 0.2033i\r\n   0.7013 + 0.0000i\r\n   1.4508 + 0.0000i\r\n\r\n\r\nlambda_BTAT =\r\n\r\n    0.3168\r\n    0.9823\r\n    1.2325\r\n         0\r\n\r\n<\/pre><p>The triangular matrices for <tt>lambda_AB<\/tt> are<\/p><pre class=\"codeinput\">   [QAZ,QBZ] = qz(A,B);\r\n   QAZ\r\n   QBZ\r\n<\/pre><pre class=\"codeoutput\">\r\nQAZ =\r\n\r\n    0.7437    4.1769  -12.7279   -5.5000\r\n         0    0.0000    5.2328    2.1602\r\n         0         0    0.7857    0.0123\r\n         0         0         0   -0.2887\r\n\r\n\r\nQBZ =\r\n\r\n    0.5005    6.6143   -8.4853   -2.5000\r\n         0    0.0000    3.2668    2.0105\r\n         0         0    1.1525   -0.7904\r\n         0         0         0    0.2887\r\n\r\n<\/pre><p>Examine the diagonals more carefully. <tt>alfa(2)\/beta(2)<\/tt> is the only roundoff over roundoff, but all four eigenvalues are unstable.<\/p><pre class=\"codeinput\">   format <span class=\"string\">long<\/span> <span class=\"string\">e<\/span>\r\n   alfa = diag(QAZ)\r\n   beta = diag(QBZ)\r\n   format <span class=\"string\">short<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nalfa =\r\n\r\n     7.437114999643711e-01\r\n     1.216947725307920e-14\r\n     7.857314232211017e-01\r\n    -2.886751345948121e-01\r\n\r\n\r\nbeta =\r\n\r\n     5.005405248737872e-01\r\n     1.021080292327182e-13\r\n     1.152509249099882e+00\r\n     2.886751345948153e-01\r\n\r\n<\/pre><h4>References<a name=\"2c8b301b-125b-4389-a5ea-fd8eccc8d4ba\"><\/a><\/h4><p>C. B. Moler and G. W. Stewart, \"An Algorithm for Generalized Matrix Eigenvalue Problems\", <i>SIAM J. Numerical Analysis<\/i>, Vol.10, No.2, April 1973. Also available at <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/cbm_gws.pdf\">cbm_gws.pdf<\/a><\/p><p>J. H. Wilkinson, \"Kronecker's Canonical Form and the QZ Algorithm\", <i>Linear Algebra and its Applications<\/i>, Vol. 28, 1979. Also available at <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/wilkinson.pdf\">wilkinson.pdf<\/a><\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_8891e70a294b4c03bb99ac1e6e01b5a5() {\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='8891e70a294b4c03bb99ac1e6e01b5a5 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 8891e70a294b4c03bb99ac1e6e01b5a5';\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 2023 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_8891e70a294b4c03bb99ac1e6e01b5a5()\"><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; R2023a<br><\/p><\/div><!--\r\n8891e70a294b4c03bb99ac1e6e01b5a5 ##### SOURCE BEGIN #####\r\n%% Singular Matrix Pencils and the QZ Algorithm, Update\r\n% (The January 5 posting was premature and incomplete.)\r\n%\r\n% This year, 2023, is the 50-th anniversary of the QZ algorithm\r\n% for the generalized matrix eigenvalue problem,\r\n% \r\n%    Ax = \u03bbBx\r\n%\r\n% The algorithm avoids inverting either |A| or |B|.\r\n% And, importantly, the QZ algorithm can be used to detect and analyze \r\n% exceptional instances of the problem known as _singular pencils_.\r\n% These pencils do not occur in the standard eigenvalue problem where\r\n% |B| is the identity matrix.\r\n\r\n%% Singular pencils\r\n% A matrix pencil is _singular_ if both |A| and |B| are singular and,\r\n% moreover, |A| - \u03bb |B| is singular for all \u03bb.  Equivalently,\r\n% \r\n%    det(A - \u03bbB) = 0 for all \u03bb.\r\n%\r\n% Singular pencils are more insidious than might appear at first glance.\r\n% In some sense, the spectrum is the entire complex plane.\r\n%\r\n% There are no singular pencils with the standard eigenvalue problem\r\n% \r\n%    Ax = \u03bbx\r\n%\r\n% where |B| is the identity matrix and certainly nonsingular.\r\n%\r\n% If |A| and |B| are both real symmetric or complex Hermitian, but neither\r\n% is positive definite, the pencil may or may not be singular.\r\n% Symmetric problems occur frequently and there are\r\n% separate algorithms and perturbation and convergence theories.\r\n%\r\n% The QZ algorithm does not compute the eigenvalues \u03bb until the very last\r\n% step.  It stably reduces |A| and |B| to triangular form\r\n% with diagonals \u03b1 and \u03b2. The eigenvalues are then the ratios\r\n%\r\n%    \u03bb = \u03b1.\/\u03b2\r\n%\r\n% Isolated zeros in \u03b1 or \u03b2 yield zero or infinite eigenvalues with no\r\n% special difficulties.  Singular pencils occur if and only if zeros in\r\n% \u03b1 and \u03b2 occur _with the same index_ and (with exact arithmetic) lead to\r\n% \u03bb = 0\/0 = NaN.\r\n%\r\n% With a singular pencil, some, perhaps all, of the diagonal values\r\n% in \u03b1 and \u03b2 are highly sensitive to perturbation, and all of the\r\n% eigenvalues computed from the ratios are suspect.  Theoretically\r\n% the ill-conditioned eigenvalues can be determined from the Kronecker\r\n% Canonical Form, a generalization of the notorious Jordan Canonical\r\n% Form.  But, like the Jordan Form, the Kronecker Form cannot provide        \r\n% a stable numerical algorithm.\r\n\r\n%% 3-by-3 example\r\n\r\n   A = [9 8 7; 6 5 4; 3 2 1]\r\n\r\n   B = [1 3 2; 4 6 5; 7 9 8]\r\n\r\n%%\r\n% Let's verify that this is a singular pencil.\r\n% Use the Symbolic Math Toolbox to introduce a free variable.\r\n\r\n   syms lambda\r\n   AB = A - lambda*B\r\n\r\n%%\r\n% Without further computation,\r\n% we can see that the second row is the average of the first and third\r\n% rows for all |lambda| and consequently that the determinant must be\r\n% identically zero.\r\n\r\n%%\r\n% With exact arithmetic, each of these statements would produce the\r\n% same eigenvalues.  After the introduction of some roundoff error,\r\n% two of the |lambdas| are indeterminant,\r\n% but |lambda = -1| is present in all four results.\r\n% Is |lambda = -1| a stable eigenvalue?\r\n\r\n   lambda_AB = eig(A,B)\r\n   lambda_BA = 1.\/eig(B,A)\r\n   lambda_ATBT = eig(A',B')\r\n   lambda_BTAT = 1.\/eig(B',A')\r\n\r\n%%\r\n% The triangular matrices for |lambda_AB|.\r\n\r\n   [QAZ,QBZ] = qz(A,B); \r\n   QAZ\r\n   QBZ\r\n\r\n%%\r\n% Careful examination of the diagonals reveals that |alfa(2)\/beta(2)| \r\n% is producing the |-1|, while |alfa(3)\/beta(3)| is roundoff over roundoff.\r\n\r\n   format long e\r\n   alfa = diag(QAZ)\r\n   beta = diag(QBZ)\r\n   format short\r\n\r\n\r\n%% Wilkinson example\r\n% Jim Wilkinson published a survey paper about QZ and Kronecker products\r\n% in 1979.  One of his examples is\r\n\r\n   A = [4 3 2 5; 6 4 2 7; -1 -1 -2 -2; 5 3 2 6]\r\n\r\n   B = [2 1 3 4; 3 3 3 5;  0  0 -3 -2; 3 1 3 5]\r\n\r\n%%\r\n% Use the Symbolic Math Toolbox to verify that this is a singular pencil.\r\n\r\n   syms lambda\r\n   AB = A - lambda*B\r\n\r\n%%\r\n% The determinant is identically zero for all |lambda|.\r\n\r\n   d = det(AB)\r\n\r\n%%\r\n% With exact arithmetic, each of these statements would produce the\r\n% same eigenvalues, but in practice each set is different.\r\n% None of the eigenvalues is stable.\r\n\r\n   lambda_AB = eig(A,B)\r\n   lambda_BA = 1.\/eig(B,A)\r\n   lambda_ATBT = eig(A',B')\r\n   lambda_BTAT = 1.\/eig(B',A')\r\n\r\n%%\r\n% The triangular matrices for |lambda_AB| are\r\n\r\n   [QAZ,QBZ] = qz(A,B); \r\n   QAZ\r\n   QBZ\r\n\r\n%%\r\n% Examine the diagonals more carefully. |alfa(2)\/beta(2)| is the only\r\n% roundoff over roundoff, but all four eigenvalues are unstable.\r\n\r\n   format long e\r\n   alfa = diag(QAZ)\r\n   beta = diag(QBZ)\r\n   format short\r\n\r\n%% References\r\n% C. B. Moler and G. W. Stewart,\r\n% \"An Algorithm for Generalized Matrix Eigenvalue Problems\",\r\n% _SIAM J. Numerical Analysis_, Vol.10, No.2, April 1973.\r\n% Also available at \r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/cbm_gws.pdf cbm_gws.pdf>\r\n%\r\n% J. H. Wilkinson,\r\n% \"Kronecker's Canonical Form and the QZ Algorithm\",\r\n% _Linear Algebra and its Applications_, Vol. 28, 1979.\r\n% Also available at\r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/wilkinson.pdf wilkinson.pdf>\r\n##### SOURCE END ##### 8891e70a294b4c03bb99ac1e6e01b5a5\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p>(The January 5 posting was premature and incomplete.)... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2023\/01\/10\/singular-matrix-pencils-and-the-qz-algorithm-update\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[11,13,6,16],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/9596"}],"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=9596"}],"version-history":[{"count":3,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/9596\/revisions"}],"predecessor-version":[{"id":9606,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/9596\/revisions\/9606"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=9596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=9596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=9596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}