838:
1711:
are sparse or structured, so that linear solves and matrix vector multiplies involving them are efficient, iterative algorithms can potentially perform better. These include projection-based methods, which use
1204:
239:
1669:
1610:
The subroutines required for the
Hessenberg-Schur variant of the Bartels–Stewart algorithm are implemented in the SLICOT library. These are used in the MATLAB control system toolbox.
1114:
953:
440:
1463:
711:
627:
1550:
1050:
580:
388:
1502:
1394:
1355:
666:
535:
509:
1248:
1780:
1580:
317:
152:
66:
868:
1742:
1709:
1689:
1600:
1414:
1308:
1288:
1268:
908:
888:
483:
463:
337:
279:
259:
184:
114:
94:
1005:
1966:
162:
and S. Nash introduced an improved version of the algorithm, known as the
Hessenberg–Schur algorithm. It remains a standard approach for solving
719:
2087:
2112:
1720:(ADI) iteration, and hybridizations that involve both projection and ADI. Iterative methods can also be used to directly construct
2107:
1959:
1717:
1119:
2148:
2066:
1952:
197:
2097:
2024:
1621:
2056:
2010:
1505:
72:
method that could be systematically applied to solve such equations. The algorithm works by using the
2061:
1070:
913:
396:
1975:
20:
1850:
Golub, G.; Nash, S.; Loan, C. Van (1979). "A Hessenberg–Schur method for the problem AX + XB= C".
154:
into a triangular system that can then be solved using forward or backward substitution. In 1979,
2138:
1423:
671:
587:
1511:
1013:
543:
351:
1721:
1713:
1468:
1360:
1321:
632:
514:
488:
1217:
2020:
1747:
1555:
284:
119:
33:
2015:
846:
8:
2133:
1994:
1064:
343:
159:
73:
69:
1930:
1727:
1694:
1674:
1585:
1399:
1293:
1273:
1253:
893:
873:
468:
448:
322:
264:
244:
169:
163:
99:
79:
28:
1465:
that can be solved using forward substitution. The advantage of this approach is that
958:
2143:
1922:
1877:
1825:
1417:
1934:
2030:
1912:
1904:
1867:
1859:
1815:
2071:
1989:
668:. This can be done using forward substitution on the blocks. Specifically, if
2127:
2035:
1926:
1881:
1863:
1829:
155:
1944:
1895:
Simoncini, V. (2016). "Computational
Methods for Linear Matrix Equations".
1060:
1820:
1803:
1917:
68:. Developed by R.H. Bartels and G.W. Stewart in 1971, it was the first
1908:
2051:
1872:
833:{\displaystyle (R-s_{kk}I)y_{k}=f_{k}+\sum _{j=k+1}^{n}s_{kj}y_{j},}
485:
are block-upper triangular matrices, with diagonal blocks of size
2102:
2092:
1671:
cost of the
Bartels–Stewart algorithm can be prohibitive. When
1290:
will also be symmetric. This symmetry can be exploited so that
319:
has a unique solution. The
Bartels–Stewart algorithm computes
1804:"Solution of the matrix equation AX + XB = C [F4]"
1582:
flops required to compute the real Schur decomposition of
1318:
The
Hessenberg–Schur algorithm replaces the decomposition
1007:
should be concatenated and solved for simultaneously.
1310:
is found more efficiently in step 3 of the algorithm.
1750:
1730:
1697:
1677:
1624:
1588:
1558:
1514:
1471:
1426:
1402:
1363:
1324:
1296:
1276:
1256:
1220:
1122:
1073:
1016:
961:
916:
896:
876:
849:
722:
674:
635:
590:
546:
517:
491:
471:
451:
399:
354:
325:
287:
267:
247:
200:
172:
122:
102:
82:
36:
1209:
1774:
1736:
1703:
1683:
1663:
1594:
1574:
1544:
1496:
1457:
1408:
1388:
1349:
1302:
1282:
1262:
1242:
1199:{\displaystyle 10(m^{3}+n^{3})+2.5(mn^{2}+nm^{2})}
1198:
1116:flops, so that the overall computational cost is
1108:
1044:
999:
947:
902:
882:
862:
832:
705:
660:
621:
574:
529:
503:
477:
457:
434:
382:
331:
311:
273:
253:
233:
178:
146:
108:
88:
60:
1313:
2125:
234:{\displaystyle X,C\in \mathbb {R} ^{m\times n}}
1801:
1605:
1960:
1849:
1974:
1664:{\displaystyle {\mathcal {O}}(m^{3}+n^{3})}
1967:
1953:
1916:
1894:
1871:
1819:
1613:
215:
2098:Basic Linear Algebra Subprograms (BLAS)
1802:Bartels, R. H.; Stewart, G. W. (1972).
2126:
1852:IEEE Transactions on Automatic Control
1948:
1420:. This leads to a system of the form
1054:
261:are distinct from the eigenvalues of
241:, and assume that the eigenvalues of
16:Algorithm in numerical linear algebra
1845:
1843:
1841:
1839:
1797:
1795:
13:
1627:
339:by applying the following steps:
14:
2160:
1836:
1792:
1716:iterations, methods based on the
1357:in step 1 with the decomposition
1210:Simplifications and special cases
27:is used to numerically solve the
1067:in step 1 require approximately
584:3. Solve the simplified system
189:
1109:{\displaystyle 10(m^{3}+n^{3})}
948:{\displaystyle s_{k-1,k}\neq 0}
1888:
1718:alternating direction implicit
1658:
1632:
1529:
1515:
1314:The Hessenberg–Schur algorithm
1193:
1161:
1152:
1126:
1103:
1077:
994:
962:
748:
723:
435:{\displaystyle S=V^{T}B^{T}V.}
186:is of small to moderate size.
1:
1785:
281:. Then, the matrix equation
7:
1606:Software and implementation
1458:{\displaystyle HY-YS^{T}=F}
1270:is symmetric, the solution
706:{\displaystyle s_{k-1,k}=0}
622:{\displaystyle RY-YS^{T}=F}
10:
2165:
2011:System of linear equations
1545:{\displaystyle (5/3)m^{3}}
1214:In the special case where
1045:{\displaystyle X=UYV^{T}.}
575:{\displaystyle F=U^{T}CV.}
383:{\displaystyle R=U^{T}AU,}
2080:
2062:Cache-oblivious algorithm
2044:
2003:
1982:
1808:Communications of the ACM
1497:{\displaystyle H=Q^{T}AQ}
1389:{\displaystyle H=Q^{T}AQ}
1350:{\displaystyle R=U^{T}AU}
1065:real Schur decompositions
661:{\displaystyle Y=U^{T}XV}
530:{\displaystyle 2\times 2}
504:{\displaystyle 1\times 1}
344:real Schur decompositions
74:real Schur decompositions
29:Sylvester matrix equation
25:Bartels–Stewart algorithm
2149:Numerical linear algebra
2113:General purpose software
1976:Numerical linear algebra
1864:10.1109/TAC.1979.1102170
1243:{\displaystyle B=-A^{T}}
21:numerical linear algebra
1775:{\displaystyle AX-XB=C}
1722:low rank approximations
1618:For large systems, the
1575:{\displaystyle 10m^{3}}
1552:flops, compared to the
1506:Householder reflections
1418:upper-Hessenberg matrix
312:{\displaystyle AX-XB=C}
147:{\displaystyle AX-XB=C}
61:{\displaystyle AX-XB=C}
1776:
1738:
1705:
1685:
1665:
1614:Alternative approaches
1596:
1576:
1546:
1498:
1459:
1410:
1390:
1351:
1304:
1284:
1264:
1244:
1200:
1110:
1046:
1001:
949:
904:
884:
864:
834:
803:
707:
662:
623:
576:
531:
505:
479:
459:
436:
384:
333:
313:
275:
255:
235:
180:
148:
110:
90:
62:
2108:Specialized libraries
2021:Matrix multiplication
2016:Matrix decompositions
1821:10.1145/361573.361582
1777:
1739:
1706:
1686:
1666:
1597:
1577:
1547:
1499:
1460:
1411:
1391:
1352:
1305:
1285:
1265:
1245:
1201:
1111:
1047:
1002:
950:
905:
885:
865:
863:{\displaystyle y_{k}}
835:
777:
708:
663:
624:
577:
532:
506:
480:
460:
437:
385:
334:
314:
276:
256:
236:
181:
149:
111:
91:
63:
1748:
1728:
1695:
1675:
1622:
1586:
1556:
1512:
1469:
1424:
1400:
1361:
1322:
1294:
1274:
1254:
1218:
1120:
1071:
1014:
959:
914:
894:
874:
847:
720:
672:
633:
588:
544:
515:
489:
469:
449:
397:
352:
323:
285:
265:
245:
198:
170:
120:
100:
80:
34:
1995:Numerical stability
1504:can be found using
164:Sylvester equations
1772:
1734:
1701:
1681:
1661:
1592:
1572:
1542:
1494:
1455:
1406:
1386:
1347:
1300:
1280:
1260:
1240:
1196:
1106:
1055:Computational cost
1042:
997:
945:
900:
880:
860:
830:
703:
658:
619:
572:
527:
501:
475:
455:
432:
380:
329:
309:
271:
251:
231:
176:
144:
106:
86:
70:numerically stable
58:
2121:
2120:
1909:10.1137/130912839
1737:{\displaystyle X}
1704:{\displaystyle B}
1684:{\displaystyle A}
1595:{\displaystyle A}
1409:{\displaystyle H}
1303:{\displaystyle Y}
1283:{\displaystyle X}
1263:{\displaystyle C}
903:{\displaystyle Y}
883:{\displaystyle k}
478:{\displaystyle S}
458:{\displaystyle R}
332:{\displaystyle X}
274:{\displaystyle B}
254:{\displaystyle A}
179:{\displaystyle X}
109:{\displaystyle B}
89:{\displaystyle A}
2156:
2031:Matrix splitting
1969:
1962:
1955:
1946:
1945:
1939:
1938:
1920:
1892:
1886:
1885:
1875:
1847:
1834:
1833:
1823:
1799:
1781:
1779:
1778:
1773:
1743:
1741:
1740:
1735:
1710:
1708:
1707:
1702:
1690:
1688:
1687:
1682:
1670:
1668:
1667:
1662:
1657:
1656:
1644:
1643:
1631:
1630:
1601:
1599:
1598:
1593:
1581:
1579:
1578:
1573:
1571:
1570:
1551:
1549:
1548:
1543:
1541:
1540:
1525:
1503:
1501:
1500:
1495:
1487:
1486:
1464:
1462:
1461:
1456:
1448:
1447:
1415:
1413:
1412:
1407:
1395:
1393:
1392:
1387:
1379:
1378:
1356:
1354:
1353:
1348:
1340:
1339:
1309:
1307:
1306:
1301:
1289:
1287:
1286:
1281:
1269:
1267:
1266:
1261:
1249:
1247:
1246:
1241:
1239:
1238:
1205:
1203:
1202:
1197:
1192:
1191:
1176:
1175:
1151:
1150:
1138:
1137:
1115:
1113:
1112:
1107:
1102:
1101:
1089:
1088:
1051:
1049:
1048:
1043:
1038:
1037:
1006:
1004:
1003:
1000:{\displaystyle }
998:
993:
992:
980:
979:
954:
952:
951:
946:
938:
937:
909:
907:
906:
901:
889:
887:
886:
881:
869:
867:
866:
861:
859:
858:
839:
837:
836:
831:
826:
825:
816:
815:
802:
797:
773:
772:
760:
759:
744:
743:
712:
710:
709:
704:
696:
695:
667:
665:
664:
659:
651:
650:
628:
626:
625:
620:
612:
611:
581:
579:
578:
573:
562:
561:
536:
534:
533:
528:
510:
508:
507:
502:
484:
482:
481:
476:
464:
462:
461:
456:
441:
439:
438:
433:
425:
424:
415:
414:
389:
387:
386:
381:
370:
369:
338:
336:
335:
330:
318:
316:
315:
310:
280:
278:
277:
272:
260:
258:
257:
252:
240:
238:
237:
232:
230:
229:
218:
185:
183:
182:
177:
153:
151:
150:
145:
115:
113:
112:
107:
95:
93:
92:
87:
67:
65:
64:
59:
2164:
2163:
2159:
2158:
2157:
2155:
2154:
2153:
2124:
2123:
2122:
2117:
2076:
2072:Multiprocessing
2040:
2036:Sparse problems
1999:
1978:
1973:
1943:
1942:
1893:
1889:
1848:
1837:
1800:
1793:
1788:
1749:
1746:
1745:
1729:
1726:
1725:
1714:Krylov subspace
1696:
1693:
1692:
1676:
1673:
1672:
1652:
1648:
1639:
1635:
1626:
1625:
1623:
1620:
1619:
1616:
1608:
1587:
1584:
1583:
1566:
1562:
1557:
1554:
1553:
1536:
1532:
1521:
1513:
1510:
1509:
1482:
1478:
1470:
1467:
1466:
1443:
1439:
1425:
1422:
1421:
1401:
1398:
1397:
1374:
1370:
1362:
1359:
1358:
1335:
1331:
1323:
1320:
1319:
1316:
1295:
1292:
1291:
1275:
1272:
1271:
1255:
1252:
1251:
1234:
1230:
1219:
1216:
1215:
1212:
1187:
1183:
1171:
1167:
1146:
1142:
1133:
1129:
1121:
1118:
1117:
1097:
1093:
1084:
1080:
1072:
1069:
1068:
1057:
1033:
1029:
1015:
1012:
1011:
988:
984:
969:
965:
960:
957:
956:
921:
917:
915:
912:
911:
895:
892:
891:
875:
872:
871:
854:
850:
848:
845:
844:
821:
817:
808:
804:
798:
781:
768:
764:
755:
751:
736:
732:
721:
718:
717:
679:
675:
673:
670:
669:
646:
642:
634:
631:
630:
607:
603:
589:
586:
585:
557:
553:
545:
542:
541:
516:
513:
512:
490:
487:
486:
470:
467:
466:
450:
447:
446:
420:
416:
410:
406:
398:
395:
394:
365:
361:
353:
350:
349:
324:
321:
320:
286:
283:
282:
266:
263:
262:
246:
243:
242:
219:
214:
213:
199:
196:
195:
192:
171:
168:
167:
121:
118:
117:
101:
98:
97:
81:
78:
77:
35:
32:
31:
17:
12:
11:
5:
2162:
2152:
2151:
2146:
2141:
2139:Control theory
2136:
2119:
2118:
2116:
2115:
2110:
2105:
2100:
2095:
2090:
2084:
2082:
2078:
2077:
2075:
2074:
2069:
2064:
2059:
2054:
2048:
2046:
2042:
2041:
2039:
2038:
2033:
2028:
2018:
2013:
2007:
2005:
2001:
2000:
1998:
1997:
1992:
1990:Floating point
1986:
1984:
1980:
1979:
1972:
1971:
1964:
1957:
1949:
1941:
1940:
1903:(3): 377–441.
1887:
1858:(6): 909–913.
1835:
1814:(9): 820–826.
1790:
1789:
1787:
1784:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1733:
1700:
1680:
1660:
1655:
1651:
1647:
1642:
1638:
1634:
1629:
1615:
1612:
1607:
1604:
1591:
1569:
1565:
1561:
1539:
1535:
1531:
1528:
1524:
1520:
1517:
1493:
1490:
1485:
1481:
1477:
1474:
1454:
1451:
1446:
1442:
1438:
1435:
1432:
1429:
1405:
1385:
1382:
1377:
1373:
1369:
1366:
1346:
1343:
1338:
1334:
1330:
1327:
1315:
1312:
1299:
1279:
1259:
1237:
1233:
1229:
1226:
1223:
1211:
1208:
1195:
1190:
1186:
1182:
1179:
1174:
1170:
1166:
1163:
1160:
1157:
1154:
1149:
1145:
1141:
1136:
1132:
1128:
1125:
1105:
1100:
1096:
1092:
1087:
1083:
1079:
1076:
1056:
1053:
1041:
1036:
1032:
1028:
1025:
1022:
1019:
996:
991:
987:
983:
978:
975:
972:
968:
964:
944:
941:
936:
933:
930:
927:
924:
920:
899:
879:
857:
853:
841:
840:
829:
824:
820:
814:
811:
807:
801:
796:
793:
790:
787:
784:
780:
776:
771:
767:
763:
758:
754:
750:
747:
742:
739:
735:
731:
728:
725:
702:
699:
694:
691:
688:
685:
682:
678:
657:
654:
649:
645:
641:
638:
618:
615:
610:
606:
602:
599:
596:
593:
571:
568:
565:
560:
556:
552:
549:
526:
523:
520:
500:
497:
494:
474:
454:
443:
442:
431:
428:
423:
419:
413:
409:
405:
402:
391:
390:
379:
376:
373:
368:
364:
360:
357:
342:1.Compute the
328:
308:
305:
302:
299:
296:
293:
290:
270:
250:
228:
225:
222:
217:
212:
209:
206:
203:
191:
188:
175:
143:
140:
137:
134:
131:
128:
125:
105:
85:
57:
54:
51:
48:
45:
42:
39:
15:
9:
6:
4:
3:
2:
2161:
2150:
2147:
2145:
2142:
2140:
2137:
2135:
2132:
2131:
2129:
2114:
2111:
2109:
2106:
2104:
2101:
2099:
2096:
2094:
2091:
2089:
2086:
2085:
2083:
2079:
2073:
2070:
2068:
2065:
2063:
2060:
2058:
2055:
2053:
2050:
2049:
2047:
2043:
2037:
2034:
2032:
2029:
2026:
2022:
2019:
2017:
2014:
2012:
2009:
2008:
2006:
2002:
1996:
1993:
1991:
1988:
1987:
1985:
1981:
1977:
1970:
1965:
1963:
1958:
1956:
1951:
1950:
1947:
1936:
1932:
1928:
1924:
1919:
1914:
1910:
1906:
1902:
1898:
1891:
1883:
1879:
1874:
1869:
1865:
1861:
1857:
1853:
1846:
1844:
1842:
1840:
1831:
1827:
1822:
1817:
1813:
1809:
1805:
1798:
1796:
1791:
1783:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1744:when solving
1731:
1723:
1719:
1715:
1698:
1678:
1653:
1649:
1645:
1640:
1636:
1611:
1603:
1589:
1567:
1563:
1559:
1537:
1533:
1526:
1522:
1518:
1508:at a cost of
1507:
1491:
1488:
1483:
1479:
1475:
1472:
1452:
1449:
1444:
1440:
1436:
1433:
1430:
1427:
1419:
1403:
1383:
1380:
1375:
1371:
1367:
1364:
1344:
1341:
1336:
1332:
1328:
1325:
1311:
1297:
1277:
1257:
1235:
1231:
1227:
1224:
1221:
1207:
1188:
1184:
1180:
1177:
1172:
1168:
1164:
1158:
1155:
1147:
1143:
1139:
1134:
1130:
1123:
1098:
1094:
1090:
1085:
1081:
1074:
1066:
1062:
1052:
1039:
1034:
1030:
1026:
1023:
1020:
1017:
1008:
989:
985:
981:
976:
973:
970:
966:
942:
939:
934:
931:
928:
925:
922:
918:
897:
890:th column of
877:
855:
851:
827:
822:
818:
812:
809:
805:
799:
794:
791:
788:
785:
782:
778:
774:
769:
765:
761:
756:
752:
745:
740:
737:
733:
729:
726:
716:
715:
714:
700:
697:
692:
689:
686:
683:
680:
676:
655:
652:
647:
643:
639:
636:
616:
613:
608:
604:
600:
597:
594:
591:
582:
569:
566:
563:
558:
554:
550:
547:
538:
524:
521:
518:
498:
495:
492:
472:
452:
445:The matrices
429:
426:
421:
417:
411:
407:
403:
400:
393:
392:
377:
374:
371:
366:
362:
358:
355:
348:
347:
346:
345:
340:
326:
306:
303:
300:
297:
294:
291:
288:
268:
248:
226:
223:
220:
210:
207:
204:
201:
190:The algorithm
187:
173:
165:
161:
157:
141:
138:
135:
132:
129:
126:
123:
116:to transform
103:
83:
75:
71:
55:
52:
49:
46:
43:
40:
37:
30:
26:
22:
1983:Key concepts
1918:11585/586011
1900:
1896:
1890:
1855:
1851:
1811:
1807:
1617:
1609:
1317:
1213:
1061:QR algorithm
1058:
1009:
842:
583:
539:
444:
341:
193:
24:
18:
1897:SIAM Review
160:C. Van Loan
2134:Algorithms
2128:Categories
2025:algorithms
1786:References
1059:Using the
955:, columns
2052:CPU cache
1927:0036-1445
1882:0018-9286
1873:1813/7472
1830:0001-0782
1758:−
1434:−
1228:−
982:∣
974:−
940:≠
926:−
779:∑
730:−
684:−
598:−
522:×
496:×
295:−
224:×
211:∈
130:−
44:−
2144:Matrices
2081:Software
2045:Hardware
2004:Problems
1935:17271167
1396:, where
629:, where
156:G. Golub
1010:4. Set
910:. When
870:is the
713:, then
540:2. Set
2103:LAPACK
2093:MATLAB
1933:
1925:
1880:
1828:
1416:is an
1063:, the
843:where
23:, the
2088:ATLAS
1931:S2CID
166:when
2067:SIMD
1923:ISSN
1878:ISSN
1826:ISSN
1691:and
1250:and
465:and
194:Let
96:and
2057:TLB
1913:hdl
1905:doi
1868:hdl
1860:doi
1816:doi
1782:.
1724:to
1602:.
1206:.
1159:2.5
511:or
76:of
19:In
2130::
1929:.
1921:.
1911:.
1901:58
1899:.
1876:.
1866:.
1856:24
1854:.
1838:^
1824:.
1812:15
1810:.
1806:.
1794:^
1560:10
1124:10
1075:10
537:.
158:,
2027:)
2023:(
1968:e
1961:t
1954:v
1937:.
1915::
1907::
1884:.
1870::
1862::
1832:.
1818::
1770:C
1767:=
1764:B
1761:X
1755:X
1752:A
1732:X
1699:B
1679:A
1659:)
1654:3
1650:n
1646:+
1641:3
1637:m
1633:(
1628:O
1590:A
1568:3
1564:m
1538:3
1534:m
1530:)
1527:3
1523:/
1519:5
1516:(
1492:Q
1489:A
1484:T
1480:Q
1476:=
1473:H
1453:F
1450:=
1445:T
1441:S
1437:Y
1431:Y
1428:H
1404:H
1384:Q
1381:A
1376:T
1372:Q
1368:=
1365:H
1345:U
1342:A
1337:T
1333:U
1329:=
1326:R
1298:Y
1278:X
1258:C
1236:T
1232:A
1225:=
1222:B
1194:)
1189:2
1185:m
1181:n
1178:+
1173:2
1169:n
1165:m
1162:(
1156:+
1153:)
1148:3
1144:n
1140:+
1135:3
1131:m
1127:(
1104:)
1099:3
1095:n
1091:+
1086:3
1082:m
1078:(
1040:.
1035:T
1031:V
1027:Y
1024:U
1021:=
1018:X
995:]
990:k
986:y
977:1
971:k
967:y
963:[
943:0
935:k
932:,
929:1
923:k
919:s
898:Y
878:k
856:k
852:y
828:,
823:j
819:y
813:j
810:k
806:s
800:n
795:1
792:+
789:k
786:=
783:j
775:+
770:k
766:f
762:=
757:k
753:y
749:)
746:I
741:k
738:k
734:s
727:R
724:(
701:0
698:=
693:k
690:,
687:1
681:k
677:s
656:V
653:X
648:T
644:U
640:=
637:Y
617:F
614:=
609:T
605:S
601:Y
595:Y
592:R
570:.
567:V
564:C
559:T
555:U
551:=
548:F
525:2
519:2
499:1
493:1
473:S
453:R
430:.
427:V
422:T
418:B
412:T
408:V
404:=
401:S
378:,
375:U
372:A
367:T
363:U
359:=
356:R
327:X
307:C
304:=
301:B
298:X
292:X
289:A
269:B
249:A
227:n
221:m
216:R
208:C
205:,
202:X
174:X
142:C
139:=
136:B
133:X
127:X
124:A
104:B
84:A
56:C
53:=
50:B
47:X
41:X
38:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.