Symbolic Cholesky decomposition

This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Symbolic Cholesky decomposition" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

In the mathematical subfield of numerical analysis the symbolic Cholesky decomposition is an algorithm used to determine the non-zero pattern for the $L$ factors of a symmetric sparse matrix when applying the Cholesky decomposition or variants.

Algorithm

Let $A=(a_{ij})\in \mathbb {K} ^{n\times n}$ be a sparse symmetric positive definite matrix with elements from a field $\mathbb {K}$ , which we wish to factorize as $A=LL^{T}\,$ .

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:

Let ${\mathcal {A}}_{i}$ and ${\mathcal {L}}_{j}$ be sets representing the non-zero patterns of columns $i$ and $j$ (below the diagonal only, and including diagonal elements) of matrices $A$ and $L$ respectively.
Take $\min {\mathcal {L}}_{j}$ to mean the smallest element of ${\mathcal {L}}_{j}$ .
Use a parent function $\pi (i)\,\!$ to define the elimination tree within the matrix.

The following algorithm gives an efficient symbolic factorization of $A$ :

{\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}}

Read other articles:

Mikhail Kasyanov

Nama ini menggunakan aturan penamaan Slavia Timur; nama patronimiknya adalah Mikhailovich dan nama keluarganya adalah Kasyanov. Mikhaíl Kas'yánov Михаи́л Касья́новKas'yanov pada 2015 Perdana Menteri RussiaMasa jabatan7 Mei 2000 – 24 Februari 2004PresidenVladimir Putin PendahuluVladimir PutinPenggantiMikhail FradkovWakil Perdana Menteri Pertama RusiaMasa jabatan10 Januari 2000 – 17 Mei 2000Perdana MenteriVladimir Putin PendahuluVladimir PutinPenggant...

Lee Camp (footballer)

British footballer (born 1984) Lee Camp Camp in 2007Personal informationFull name Lee Michael John Camp[1]Date of birth (1984-08-22) 22 August 1984 (age 39)Place of birth Derby, EnglandHeight 6 ft 0 in (1.83 m)[2]Position(s) GoalkeeperYouth career0000–2002 Derby CountySenior career*Years Team Apps (Gls)2002–2007 Derby County 89 (0)2003 → Burton Albion (loan) 5 (0)2004 → Queens Park Rangers (loan) 12 (0)2006 → Norwich City (loan) 3 (0)2007 → Quee...

Spiritual Heritage

Political party in Russia Spiritual Heritage Духовное наследиеLeaderAlexey PodberezkinFounded27 May 1995 (1995-05-27)[1]DissolvedMarch 2, 2002 (2002-03-02)Succeeded byUnited Socialist PartyParty of Social JusticeHeadquarters16th Building, Bakhrushina Street, Moscow, Russia. 113054IdeologyRussian nationalismModerate nationalism[2]PatriotismStatismColours Blue RedSloganScience, culture, education, healthcare and...

Terfenadine

Chemical compound TerfenadineClinical dataTrade namesSeldane, Triludan, TeldaneAHFS/Drugs.comMultum Consumer InformationMedlinePlusa600034Routes ofadministrationBy mouthATC codeR06AX12 (WHO) Legal statusLegal status Withdrawn Pharmacokinetic dataProtein binding70%MetabolismHepatic (CYP3A4)MetabolitesFexofenadineElimination half-life3.5 hoursIdentifiers IUPAC name (RS)-1-(4-tert-butylphenyl)-4-{4-[hydroxy(diphenyl)methyl]piperidin-1-yl}-butan-1-ol CAS Number50679-08-8 YPubChem C...

История Чукотки

История Чукотки восходит к эпохе палеолита. Содержание 1 Чукотка в древности 2 Взаимоотношения Чукотки и Российской империи 3 Чукотка в составе Российской империи 4 Революция на Чукотке 5 Чукотка в cоветский период 6 Чукотский автономный округ в Российской Федерации 7 См. т...

State Street Corporation

Global financial services company This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: State Street Corporation – news · newspapers · books · scholar · JSTOR (May 2021) (Learn how and when to remove this te...

NGC 34

NGC 34NGC 34 Teleskop Luar Angkasa HubbleData pengamatan (J2000 epos)Rasi bintangCetusAsensio rekta 00j 11m 06.5d[1]Deklinasi -12° 06′ 26″[1]Pergeseran merah0.019617[1]Kecepatan radial helio5,881 ± 2 km/s[1]Jarak240 juta tahun cahaya (80 juta parsec)[1]Magnitudo semu (V)15.3[1]Ciri-ciriJenisSc[1]Ukuran semu (V)2′.2 × 0′.8[1]Penamaan lainNGC 17,[1] PGC 781,[1] MCG ...

Sergej Donatovič Dovlatov

Sergej Donatovič Dovlatov in russo Серге́й Дона́тович Довла́тов? detto Mečik in russo Мечик? (Ufa, 3 settembre 1941 – New York, 24 agosto 1990) è stato un giornalista e scrittore sovietico. Indice 1 Biografia 2 Opere 3 Edizioni italiane 4 Altri libri 5 Altri progetti 6 Collegamenti esterni Biografia La madre Nora (Нора Сергеевна Довлатова, 1908—1999), di origine armena, era una correttrice di testi letterari, il padre Donat...

Persian alphabet

Writing system used for the Persian language For other scripts that have been used to write the Persian language, see Persian language § Orthography. Perso-Arabic script redirects here. For the Arabic script, see Arabic script. This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs additional citations for verification. Please help improve this article by adding citation...

Vehicular harbour crossings in Hong Kong

There are three vehicular harbour crossings in Hong Kong, linking the Kowloon peninsula with Hong Kong Island. These are as follows: Cross-Harbour Tunnel – a 1.8 kilometres (1.1 mi) long tunnel between Hung Hom and Causeway Bay. Opened 1972. Government owned; franchise expired 1999; Eastern Harbour Crossing – a 2.2 kilometres (1.4 mi) long tunnel between Cha Kwo Ling and Quarry Bay. Opened 1989. Franchise awarded to a private consortium and expired on August 7, 2016; Western Ha...

Stefanie Sun

Stefanie SunRehearsal at Kenting Peninsula Music Carnival, Taiwan (2010)Nama Tionghoa孫燕姿 (Tradisional)Nama Tionghoa孙燕姿 (Sederhana)PinyinSūn Yànzī (Mandarin)Nama LahirSng Ee TzeLeluhurCinaLahir1978SingapuraPekerjaanPenyanyi dan penulis lirikGenreMandopopInstrumenSuara, PianoLabelWonderful Music (2011–present) Capitol Music (2006–2008)Warner Music Taiwan (2000–2006)Tahun aktif2000–kiniHubungan peranlihat KolaborasiSitus webStefanie Sun's blogPasanganNadim Van Der Ros ...

Wasting Time (Brent Faiyaz song)

2021 single by Brent Faiyaz featuring Drake Wasting TimeSingle by Brent Faiyaz featuring Drake and The Neptunesfrom the album Wasteland ReleasedJuly 1, 2021Length5:01LabelLost KidsVeniceStemSongwriter(s) Christopher Wood Aubrey Graham Pharrell Williams Chad Hugo Producer(s)The NeptunesBrent Faiyaz singles chronology Show U Off (2021) Wasting Time (2021) Price of Fame (2022) Drake singles chronology Having Our Way(2021) Wasting Time(2021) Over the Top(2021) Wasting Time is a song by Am...

Державний комітет телебачення і радіомовлення України

Державний комітет телебачення і радіомовлення України (Держкомтелерадіо) Приміщення комітетуЗагальна інформаціяКраїна УкраїнаДата створення 2003Керівне відомство Кабінет Міністрів УкраїниРічний бюджет 1 964 898 500 ₴[1]Голова Олег НаливайкоПідвідомчі ор...

Jacki Piper

English actress (born 1946) Jacki PiperJacki Piper at the NEC in Birmingham, March 2009BornJacqueline Crump (1946-08-03) 3 August 1946 (age 77)Birmingham, Warwickshire, England, United KingdomOccupationActorYears active1967–2012 Jacqueline Crump (born 3 August 1946),[1] known professionally by her stage name Jacki Piper, is an English actress, best known for her appearances as the female juvenile lead in the British film comedies Carry On Up the Jungle (1970), Carry On Lov...

Hippolyte de Villemessant

Questa voce sull'argomento giornalisti francesi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Hippolyte de Villemessant Jean Hippolyte Auguste Delaunay de Villemessant (Rouen, 22 aprile 1810 – Monte Carlo, 12 aprile 1879) è stato un giornalista francese, noto come patron del quotidiano Le Figaro. Altri progetti Altri progetti Wikiquote Wikimedia Commons Wikiquote contiene citazioni di o su Hippolyte de Villemessant Wikimedia Commons contiene imma...

クィア理論

LGBT関連シリーズLGBTのトピックレズビアン ∙ ゲイ ∙ バイセクシュアル ∙ トランスジェンダー性的指向ホモセクシュアルバイセクシュアルパンセクシュアルアセクシュアルグレイ・アセクシュアル（英語版）クィアセクシュアル・アイデンティティ人口統計（英語版）生物学（英語版）環境歴史（英語版）年表 LGBTの社会運動スト�...

2009 Liberal Party of Canada leadership election

2009 Liberal Party of Canada leadership election ← 2006 May 2, 2009 2013 → Candidate Michael Ignatieff Delegate count 1,964 Percentage 97% Leader before election Michael Ignatieff (interim) Elected Leader Michael Ignatieff 2009 Liberal leadership electionDateApril 30 – May 2, 2009ConventionVancouver Convention CentreVancouver, British ColumbiaResigning leaderStéphane DionWon byMichael IgnatieffBallots1Candidates1Entrance Fee$90,000Spending limit...

Lew Tabackin

American jazz saxophonist and flutist Lew TabackinBackground informationBirth nameLewis Barry TabackinBorn (1940-03-26) March 26, 1940 (age 84)Philadelphia, Pennsylvania, U.S.GenresJazzOccupationMusicianInstrument(s)Tenor saxophone, fluteYears active1962–presentLabelsRCA Victor/BMG, Discomate, Inner CityWebsitewww.lewtabackin.comMusical artist Lewis Barry Tabackin (born March 26, 1940)[1] is an American jazz tenor saxophonist and flutist. He is married to pianist Toshiko Akiyos...

Triffoire

Le Triffoireruisseau le Triffoire Caractéristiques Longueur 7,9 km [1] Bassin collecteur Seine Débit moyen 3,75 m3/s (Feuillade) Régime pluvial océanique Cours Source (source) · Localisation Saint-Germain · Altitude 117 m · Coordonnées 48° 14′ 45″ N, 4° 02′ 20″ E Confluence la Seine · Localisation Troyes · Altitude 109 m · Coordonnées 48° 16′ 59″ N, 4° 05′ 30″ E Géographie Princip...

Book of the de Burgos

Late 16th-century Gaelic illuminated manuscript in the Library of Trinity College, Dublin Book of the de BurgosTrinity College LibraryFolio 19rAlso known asBook of the BurkesDatebetween 1571 and 1584Place of originConnachtLanguage(s)Early Modern Irish, LatinPatronSeaán mac Oliver BourkeMaterialVellumFormatFolioScriptIrish minusculeContentsgenealogy, poetryIllumination(s)Irish soldiers The Book of the de Burgos or Book of the Burkes (Irish: Leabhar na Búrca; Latin: Liber Burgensis) is a late...

Gereja Katolik di Rusia

Template talk:Bronisław Malinowski

Template talk:European Track Championships – Men's 1 km time trial

Sindangjaya, Cipanas, Cianjur

List of compositions by Victor Herbert

Mandrehe Barat, Nias Barat