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