818:
507:
22:
813:{\displaystyle {\begin{aligned}&\pi (i):=0~{\mbox{for all}}~i\\&{\mbox{For}}~i:=1~{\mbox{to}}~n\\&\qquad {\mathcal {L}}_{i}:={\mathcal {A}}_{i}\\&\qquad {\mbox{For all}}~j~{\mbox{such that}}~\pi (j)=i\\&\qquad \qquad {\mathcal {L}}_{i}:=({\mathcal {L}}_{i}\cup {\mathcal {L}}_{j})\setminus \{j\}\\&\qquad \pi (i):=\min({\mathcal {L}}_{i}\setminus \{i\})\end{aligned}}}
308:
In order to implement an efficient sparse factorization it has been found to be necessary to determine the non zero structure of the factors before doing any numerical work. To write the algorithm down we use the following notation:
242:
512:
426:
457:
373:
342:
265:
491:
303:
43:
160:
94:
66:
73:
113:
80:
832:
47:
184:
62:
32:
51:
36:
397:
87:
170:
431:
347:
316:
248:
465:
131:
271:
163:
145:
826:
166:
127:
21:
139:
244:
be a sparse symmetric positive definite matrix with elements from a field
383:(below the diagonal only, and including diagonal elements) of matrices
497:
The following algorithm gives an efficient symbolic factorization of
15:
780:
724:
707:
687:
616:
599:
438:
407:
354:
323:
650:
634:
578:
556:
538:
375:
be sets representing the non-zero patterns of columns
237:{\displaystyle A=(a_{ij})\in \mathbb {K} ^{n\times n}}
510:
468:
434:
400:
350:
319:
274:
251:
187:
148:
812:
485:
451:
420:
367:
336:
297:
259:
236:
154:
493:to define the elimination tree within the matrix.
482:
771:
401:
142:used to determine the non-zero pattern for the
8:
800:
794:
747:
741:
50:. Unsourced material may be challenged and
785:
779:
778:
729:
723:
722:
712:
706:
705:
692:
686:
685:
649:
633:
621:
615:
614:
604:
598:
597:
577:
555:
537:
511:
509:
481:
467:
443:
437:
436:
433:
412:
406:
405:
399:
359:
353:
352:
349:
328:
322:
321:
318:
294:
288:
273:
253:
252:
250:
222:
218:
217:
201:
186:
147:
114:Learn how and when to remove this message
791:
738:
421:{\displaystyle \min {\mathcal {L}}_{j}}
7:
48:adding citations to reliable sources
452:{\displaystyle {\mathcal {L}}_{j}}
368:{\displaystyle {\mathcal {L}}_{j}}
337:{\displaystyle {\mathcal {A}}_{i}}
14:
63:"Symbolic Cholesky decomposition"
428:to mean the smallest element of
268:, which we wish to factorize as
20:
755:
683:
682:
632:
595:
136:symbolic Cholesky decomposition
803:
774:
765:
759:
735:
701:
668:
662:
525:
519:
478:
472:
210:
194:
1:
260:{\displaystyle \mathbb {K} }
486:{\displaystyle \pi (i)\,\!}
849:
298:{\displaystyle A=LL^{T}\,}
814:
487:
462:Use a parent function
453:
422:
369:
338:
299:
261:
238:
171:Cholesky decomposition
156:
833:Matrix decompositions
815:
488:
454:
423:
370:
339:
300:
262:
239:
157:
508:
466:
432:
398:
348:
317:
272:
249:
185:
146:
44:improve this article
810:
808:
654:
638:
582:
560:
542:
483:
449:
418:
365:
334:
295:
257:
234:
169:when applying the
152:
132:numerical analysis
658:
653:
648:
642:
637:
586:
581:
576:
564:
559:
546:
541:
536:
155:{\displaystyle L}
124:
123:
116:
98:
840:
819:
817:
816:
811:
809:
790:
789:
784:
783:
753:
734:
733:
728:
727:
717:
716:
711:
710:
697:
696:
691:
690:
680:
656:
655:
651:
646:
640:
639:
635:
630:
626:
625:
620:
619:
609:
608:
603:
602:
593:
584:
583:
579:
574:
562:
561:
557:
553:
544:
543:
539:
534:
514:
500:
492:
490:
489:
484:
458:
456:
455:
450:
448:
447:
442:
441:
427:
425:
424:
419:
417:
416:
411:
410:
390:
386:
382:
378:
374:
372:
371:
366:
364:
363:
358:
357:
343:
341:
340:
335:
333:
332:
327:
326:
304:
302:
301:
296:
293:
292:
267:
266:
264:
263:
258:
256:
243:
241:
240:
235:
233:
232:
221:
209:
208:
161:
159:
158:
153:
119:
112:
108:
105:
99:
97:
56:
24:
16:
848:
847:
843:
842:
841:
839:
838:
837:
823:
822:
807:
806:
777:
751:
750:
721:
704:
684:
678:
677:
628:
627:
613:
596:
591:
590:
551:
550:
506:
505:
498:
464:
463:
435:
430:
429:
404:
396:
395:
388:
384:
380:
376:
351:
346:
345:
320:
315:
314:
284:
270:
269:
247:
246:
245:
216:
197:
183:
182:
179:
144:
143:
120:
109:
103:
100:
57:
55:
41:
25:
12:
11:
5:
846:
844:
836:
835:
825:
824:
821:
820:
805:
802:
799:
796:
793:
788:
782:
776:
773:
770:
767:
764:
761:
758:
754:
752:
749:
746:
743:
740:
737:
732:
726:
720:
715:
709:
703:
700:
695:
689:
681:
679:
676:
673:
670:
667:
664:
661:
645:
631:
629:
624:
618:
612:
607:
601:
594:
592:
589:
573:
570:
567:
554:
552:
549:
533:
530:
527:
524:
521:
518:
515:
513:
495:
494:
480:
477:
474:
471:
460:
446:
440:
415:
409:
403:
392:
362:
356:
331:
325:
291:
287:
283:
280:
277:
255:
231:
228:
225:
220:
215:
212:
207:
204:
200:
196:
193:
190:
178:
175:
151:
122:
121:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
845:
834:
831:
830:
828:
797:
786:
768:
762:
756:
744:
730:
718:
713:
698:
693:
674:
671:
665:
659:
643:
622:
610:
605:
587:
571:
568:
565:
547:
531:
528:
522:
516:
504:
503:
502:
475:
469:
461:
444:
413:
393:
391:respectively.
360:
329:
312:
311:
310:
306:
289:
285:
281:
278:
275:
229:
226:
223:
213:
205:
202:
198:
191:
188:
176:
174:
173:or variants.
172:
168:
167:sparse matrix
165:
162:factors of a
149:
141:
137:
133:
129:
118:
115:
107:
104:December 2009
96:
93:
89:
86:
82:
79:
75:
72:
68:
65: –
64:
60:
59:Find sources:
53:
49:
45:
39:
38:
34:
29:This article
27:
23:
18:
17:
496:
307:
180:
135:
130:subfield of
128:mathematical
125:
110:
101:
91:
84:
77:
70:
58:
42:Please help
30:
74:newspapers
792:∖
757:π
739:∖
719:∪
660:π
652:such that
517:π
501: :
470:π
227:×
214:∈
177:Algorithm
164:symmetric
140:algorithm
31:does not
827:Category
636:For all
540:for all
126:In the
88:scholar
52:removed
37:sources
657:
647:
641:
585:
575:
563:
545:
535:
138:is an
90:
83:
76:
69:
61:
394:Take
95:JSTOR
81:books
387:and
379:and
344:and
313:Let
181:Let
134:the
67:news
35:any
33:cite
772:min
558:For
402:min
46:by
829::
769::=
699::=
611::=
580:to
569::=
529::=
305:.
804:)
801:}
798:i
795:{
787:i
781:L
775:(
766:)
763:i
760:(
748:}
745:j
742:{
736:)
731:j
725:L
714:i
708:L
702:(
694:i
688:L
675:i
672:=
669:)
666:j
663:(
644:j
623:i
617:A
606:i
600:L
588:n
572:1
566:i
548:i
532:0
526:)
523:i
520:(
499:A
479:)
476:i
473:(
459:.
445:j
439:L
414:j
408:L
389:L
385:A
381:j
377:i
361:j
355:L
330:i
324:A
290:T
286:L
282:L
279:=
276:A
254:K
230:n
224:n
219:K
211:)
206:j
203:i
199:a
195:(
192:=
189:A
150:L
117:)
111:(
106:)
102:(
92:·
85:·
78:·
71:·
54:.
40:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
