Deprecated: Creation of dynamic property NewFoldLabs\WP\Module\MyProducts\ProductsApi::$namespace is deprecated in /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php on line 41

Deprecated: Creation of dynamic property NewFoldLabs\WP\Module\MyProducts\ProductsApi::$rest_base is deprecated in /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php on line 42

Warning: Cannot modify header information - headers already sent by (output started at /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php:41) in /home2/rainyuxu/public_html/wp-includes/rest-api/class-wp-rest-server.php on line 1831

Warning: Cannot modify header information - headers already sent by (output started at /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php:41) in /home2/rainyuxu/public_html/wp-includes/rest-api/class-wp-rest-server.php on line 1831

Warning: Cannot modify header information - headers already sent by (output started at /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php:41) in /home2/rainyuxu/public_html/wp-includes/rest-api/class-wp-rest-server.php on line 1831

Warning: Cannot modify header information - headers already sent by (output started at /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php:41) in /home2/rainyuxu/public_html/wp-includes/rest-api/class-wp-rest-server.php on line 1831

Warning: Cannot modify header information - headers already sent by (output started at /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php:41) in /home2/rainyuxu/public_html/wp-includes/rest-api/class-wp-rest-server.php on line 1831

Warning: Cannot modify header information - headers already sent by (output started at /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php:41) in /home2/rainyuxu/public_html/wp-includes/rest-api/class-wp-rest-server.php on line 1831

Warning: Cannot modify header information - headers already sent by (output started at /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php:41) in /home2/rainyuxu/public_html/wp-includes/rest-api/class-wp-rest-server.php on line 1831

Warning: Cannot modify header information - headers already sent by (output started at /home2/rainyuxu/public_html/wp-content/plugins/bluehost-wordpress-plugin/vendor/newfold-labs/wp-module-my-products/includes/ProductsApi.php:41) in /home2/rainyuxu/public_html/wp-includes/rest-api/class-wp-rest-server.php on line 1831
{"id":733,"date":"2023-05-03T18:12:46","date_gmt":"2023-05-03T22:12:46","guid":{"rendered":"https:\/\/rainyuxuan.com\/?p=733"},"modified":"2023-11-24T19:03:49","modified_gmt":"2023-11-25T00:03:49","slug":"cholesky-factorization-and-elimination-tree","status":"publish","type":"post","link":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/","title":{"rendered":"Cholesky Factorization and Elimination Tree"},"content":{"rendered":"\n

In the last chapter, we introduced the concept of dependency. In this chapter, we will look into it and see how we can utilize this concept in factorization.<\/p>\n\n\n\n

Left-looking Cholesky factorization<\/h2>\n\n\n\n

Particularly, we will use the Left-Looking Cholesky Factorization<\/em><\/strong>. In the left-looking Cholesky factorization, we compute the factor \"\bold{L}\" column-by-column from left to right, using the already computed information (\"\bold{I}_1\", \"\bold{L}_2\", and \"\bold{A}\" in the figure below).<\/p>\n\n\n\n

\"\"
Figure 1<\/figcaption><\/figure>\n\n\n\n

In practice, we can fold together these two expressions above into a single matrix-vector multiplication and addition. We call \"\bold{c}\" the update matrix (in this case, it’s a vector; but when using supernodes, it will become a matrix).<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Another Cholesky method is the Up-Looking Cholesky Factorization<\/em>.<\/p>\n\n\n\n

Overview of sparse factorization<\/h2>\n\n\n\n

For sparse factorization, we usually go through two phases:<\/p>\n\n\n\n

    \n
  1. Symbolic Analysis<\/em>: Analyzing the non-zero pattern of matrix \"\bold{A}\" and factor \"\bold{L}\", including the elimination tree, column and row counts, fill-reducing permutation, and supernodes.<\/li>\n\n\n\n
  2. Numerical Factorization<\/em>: Computing the numerical values in \"\bold{L}\".<\/li>\n<\/ol>\n\n\n\n
    \"\"
    Figure 2, (Davis, 2016)<\/figcaption><\/figure>\n\n\n\n

    Elimination tree<\/h2>\n\n\n\n

    The elimination tree<\/strong><\/em> (etree) of the matrix is a pruned version of the Dependency Graph \"G_L\". The idea is to eliminate the transitive edges<\/strong> that can be implied by a path of other edges in the factor’s dependency graph. The implication is based on: the non-zero entry \"a_{ij}\" indicates a path from node j<\/em> to i<\/em>.<\/p>\n\n\n\n

    Although it looks like the path is longer than a single edge, remember that we are not trying to find the shortest path. We are trying to find a minimal graph that can represent the dependencies or the order of computation, and the path can cover more dependencies than a single edge. Intuitively, you can visualize the algorithm as only keeping each column’s topmost non-diagonal non-zero entry.<\/p>\n\n\n\n

    \"\"
    Figure 3, (Davis, 2016)<\/figcaption><\/figure>\n\n\n\n
    \n

    Thinking question: why does selecting the longer path make you select the smallest\/topmost non-diagonal entry?<\/p>\n<\/blockquote>\n\n\n\n

    \"\"
    Figure 4<\/figcaption><\/figure>\n\n\n\n

    With etree, you can easily find the dependencies of node j<\/em> (the nodes that need to be computed before j<\/em>) by traversing down<\/strong> the descendants, and find the nodes that will be affected by node j<\/em> by traversing up<\/strong> the ancestors. Therefore, we can determine that the order of computation is from the leaves of the tree to the root.<\/p>\n\n\n\n

    The elimination tree is stored as an array of parents<\/code>, where parents[i]<\/code> is the parent node of the node i<\/code>.<\/p>\n\n\n\n

    Constructing the elimination tree<\/h3>\n\n\n\n

    The etree describes the dependency pattern of the factor \"\bold{L}\", but we can compute etree from \"\bold{A}\" iteratively before factorization (see cs_etree<\/code> for details). <\/p>\n\n\n\n

    We iterate over the columns in the upper triangular matrix<\/span> of \"\bold{A}\" and then look at the non-zero rows in each column. Note that this is equivalent to iterating over the rows in the lower triangular matrix and then looking at the columns, but the upper matrix is easier to traverse with the CSC format. <\/p>\n\n\n\n

    The iterative computation of the etree is as follows:<\/p>\n\n\n\n

    \n

    Suppose \"T_{k-1}\" (the etree of submatrix \"\bold{L}_{1...k-1,) is known. This tree is a subset of \"T_k\". To compute \"T_k\" from \"T_{k-1}\", the children of k<\/em> (which are root nodes in \"T_{k-1}\") must be found. Since \"a_{ki} implies the path \"i\longrightarrow exists in T<\/em> , this path can be traversed in \"T_{k-1}\" until reaching a root node. This node must be a child of k<\/em>, since the path \"i\longrightarrow must exist.<\/p>\nDavis, 2006<\/cite><\/blockquote>\n\n\n\n

    Beyond this, To speed up the subtree traversal (all nodes within the path started from i<\/em> will be rooted at k<\/em>), we keep an array of ancestors<\/code>, and set ancestors[i] = k<\/code> to put the subtree \"T_{k-1}\" under \"T_{k}\". This process is path compression<\/em>. Also, notice that the ancestor of a node is the root node of the largest-k<\/em> row subtree \"T^k\" the node is in. <\/p>\n\n\n\n

    \"\"
    Figure 5, (Davis, 2016): The 9th iteration of cs_etree. Red lines show the parents<\/code>, yellow lines show the ancestors<\/code>.<\/figcaption><\/figure>\n\n\n\n

    The row subtree<\/em><\/strong> of node k<\/em>, \"T^k\" is a subtree of the etree which consists of the paths from those nodes j<\/em>, where j<\/em>‘s descendants are all zeros in column k<\/em>. <\/p>\n\n\n\n

    \n

    Node j<\/em> is a leaf of \"T^k\" if and only if both \"a_{jk} and \"a_{ik} for every descendant i<\/em> of j<\/em> in the elimination tree \"T\".<\/p>\nDavis, 2006<\/cite><\/blockquote>\n\n\n\n

    Post-ordering<\/h3>\n\n\n\n

    One simple trick to improve the performance of the factorization is post-ordering<\/strong><\/em>. After building the elimination tree, we can permutate <\/em>the matrix \"\bold{A}\" to exploit memory locality<\/strong>. Since the tree hierarchy determines the order of computation, we can place the nodes that have a dependency relationship closer to make memory access more consecutive. <\/p>\n\n\n\n

    For example, in the figure above, the etree will guide the computation to follow the order \"2. The nodes 2, 3, and 5 required by node 8 are computed a long time ago, and the pointer jumps back and forth. Hence the ideal computation order is \"2, where each node is computed right after its dependencies are ready.<\/p>\n\n\n\n

    The postordering of an etree can be easily found by performing a depth-first search<\/em>. Column j<\/em> will be moved to i<\/em> where i<\/em> is the tree node’s position’s order of traversal during a DFS.<\/p>\n\n\n\n

    Permutation<\/h4>\n\n\n\n

    In this context, permutation <\/strong><\/em>means switching nodes’ order; this is feasible because the real problem focuses on the relationship (edges) of the nodes, not their ordering. We can store the permutation of \"\bold{A}\" by a matrix \"\bold{P}\" and perform matrix multiplications \"\bold{PAP^\intercal}\".<\/p>\n\n\n\n

    \"\"
    Figure 6, (Davis, 2006): Nodes move, edges persist.<\/figcaption><\/figure>\n\n\n\n

    Non-zero patterns<\/h2>\n\n\n\n

    Fill-ins<\/h3>\n\n\n\n

    When factorizing a matrix, it will create some non-zero entries in the factor that does not exist in the original matrix (the crossed dots in Figure 2). We can these new entries the fill-in<\/strong><\/em>s. We can do a Cholesky factorization to see how they appear.<\/p>\n\n\n\n

    A key observation of the non-zero pattern in the factor is:<\/p>\n\n\n\n

    \n
    l_{ji} \\neq 0 \\text{ and } l_{ki} \\neq 0 \\Rightarrow l_{kj} \\neq 0<\/pre><\/div>\n<\/blockquote>\n\n\n\n
    For a matrix \"\bold{A}\", according to the left-looking Cholesky,<\/p>\n\n\n\n
    \\bold{l_k} = (\\bold{a_i} - \\bold{L_2} \\bold{I_1^\\intercal}) \/ l_{kk}<\/pre><\/div>\n\n\n\n
    Particularly, given that \"l_{ji} (\"l_{ji}\" is in \"\bold{I_1}\") and \"l_{ki} (\"l_{ki}\" is in \"\bold{L_2}\"), the theorem asserts that the entry \"l_{ji}\" in \"\bold{l_k}\" is non-zero in the factor \"\bold{L}\", even if \"a_{ji}\" is a zero.<\/p>\n\n\n\n
    In other words, given three nodes \"i, if paths \"i\longrightarrow and \"i\longrightarrow exist, then there will be a path \"j\longrightarrow in the factor that is not necessarily in the original matrix. <\/p>\n\n\n\n
    Fill-reducing ordering<\/h3>\n\n\n\n
    The fill-ins increase the amount of computation; by permutating the nodes prior to computing the elimination tree, we can reduce the number of fill-ins. The fill-in minimization problem is NP-hard, so we usually use heuristics.<\/p>\n\n\n\n
    \"\"
    Figure 7: Two matrices with the same content but different ordering create different fill-ins.<\/figcaption><\/figure>\n\n\n\n
    Nested dissection ordering<\/h4>\n\n\n\n
    Nested dissection ordering<\/em><\/strong> is a fill-reducing ordering that is useful in the field of computer graphics. We can use an analogy: “Moving your toes does not affect your head”.<\/p>\n\n\n\n
    Nested dissection ordering finds a list of nodes as a separator <\/strong>(for example, the “waist” from the analogy above), and then puts the nodes that are closely connected, and separated by the separator, near each other (“leg” with “feet”, “head” with “neck”). The separated part can then dissect recursively. <\/p>\n\n\n\n
    The goal of the ordering is to build a balanced <\/strong>etree, the dissected parts will be two disjoint subtrees, and they join together by the separator. As an effect, the matrix will result in a block structure<\/em>, where there are no edges between each block.<\/p>\n\n\n\n
    \"\"
    Figure 8, (Herholz & Alexa, 2019): Red region shows the separator. Red blocks in the bottom-left figure show fill-ins.<\/figcaption><\/figure>\n\n\n\n
    References<\/h2>\n\n\n\n
      Davis, T. A. (2006). Direct methods for sparse linear systems. Society for Industrial and Applied Mathematics.  <\/p>\n\n\n\n
      Davis, T. A., Rajamanickam, S., & Sid-Lakhdar, W. M. (2016). A survey of direct methods for sparse linear systems. Acta Numerica, 25, 383\u2013566. https:\/\/doi.org\/10.1017\/S0962492916000076<\/a><\/p>\n\n\n\n
      Herholz, P., & Alexa, M. (2019). Factor once: reusing cholesky factorizations on sub-meshes. ACM Transactions on Graphics, 37(6), 1\u20139. https:\/\/doi.org\/10.1145\/3272127.3275107<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    My study note for my CSC494 course project: Systems for Graphics.
    \nA rough introduction to Cholesky factorization and related concepts. <\/p>\n","protected":false},"author":1,"featured_media":936,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","WB4WB4WP_MODE":"","WB4WP_PAGE_SCRIPTS":"","WB4WP_PAGE_STYLES":"","WB4WP_PAGE_FONTS":"","WB4WP_PAGE_HEADER":"","WB4WP_PAGE_FOOTER":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[45,8],"tags":[17,46],"class_list":["post-733","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coursework","category-uoft","tag-computer-science","tag-coursework"],"yoast_head":"\nCholesky Factorization and Elimination Tree ~ rainyuxuan<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Cholesky Factorization and Elimination Tree ~ rainyuxuan\" \/>\n<meta property=\"og:description\" content=\"My study note for my CSC494 course project: Systems for Graphics. A rough introduction to Cholesky factorization and related concepts.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"rainyuxuan\" \/>\n<meta property=\"article:published_time\" content=\"2023-05-03T22:12:46+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-11-25T00:03:49+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1\" \/>\n\t<meta property=\"og:image:width\" content=\"1024\" \/>\n\t<meta property=\"og:image:height\" content=\"1024\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"rainyuxuan\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"rainyuxuan\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"8 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/\"},\"author\":{\"name\":\"rainyuxuan\",\"@id\":\"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d\"},\"headline\":\"Cholesky Factorization and Elimination Tree\",\"datePublished\":\"2023-05-03T22:12:46+00:00\",\"dateModified\":\"2023-11-25T00:03:49+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/\"},\"wordCount\":1400,\"publisher\":{\"@id\":\"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d\"},\"image\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1\",\"keywords\":[\"Computer Science\",\"Coursework\"],\"articleSection\":[\"Coursework\",\"UToronto\"],\"inLanguage\":\"en-CA\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/\",\"url\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/\",\"name\":\"Cholesky Factorization and Elimination Tree ~ rainyuxuan\",\"isPartOf\":{\"@id\":\"https:\/\/rainyuxuan.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1\",\"datePublished\":\"2023-05-03T22:12:46+00:00\",\"dateModified\":\"2023-11-25T00:03:49+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#breadcrumb\"},\"inLanguage\":\"en-CA\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-CA\",\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#primaryimage\",\"url\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1\",\"width\":1024,\"height\":1024},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/rainyuxuan.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Cholesky Factorization and Elimination Tree\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/rainyuxuan.com\/#website\",\"url\":\"https:\/\/rainyuxuan.com\/\",\"name\":\"rainyuxuan\",\"description\":\"My blog and something else \u2728\",\"publisher\":{\"@id\":\"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/rainyuxuan.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-CA\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d\",\"name\":\"rainyuxuan\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-CA\",\"@id\":\"https:\/\/rainyuxuan.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2022\/01\/64739925_p13.jpg?fit=1149%2C1200&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2022\/01\/64739925_p13.jpg?fit=1149%2C1200&ssl=1\",\"width\":1149,\"height\":1200,\"caption\":\"rainyuxuan\"},\"logo\":{\"@id\":\"https:\/\/rainyuxuan.com\/#\/schema\/person\/image\/\"},\"sameAs\":[\"https:\/\/www.instagram.com\/yuxuan_27\/\",\"https:\/\/www.linkedin.com\/in\/liuyuxuan2001\/\",\"yu2001xuan@outlook.com\"],\"url\":\"https:\/\/rainyuxuan.com\/posts\/author\/yu2001xuan\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Cholesky Factorization and Elimination Tree ~ rainyuxuan","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/","og_locale":"en_US","og_type":"article","og_title":"Cholesky Factorization and Elimination Tree ~ rainyuxuan","og_description":"My study note for my CSC494 course project: Systems for Graphics. A rough introduction to Cholesky factorization and related concepts.","og_url":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/","og_site_name":"rainyuxuan","article_published_time":"2023-05-03T22:12:46+00:00","article_modified_time":"2023-11-25T00:03:49+00:00","og_image":[{"url":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1","width":1024,"height":1024,"type":"image\/png"}],"author":"rainyuxuan","twitter_card":"summary_large_image","twitter_misc":{"Written by":"rainyuxuan","Est. reading time":"8 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#article","isPartOf":{"@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/"},"author":{"name":"rainyuxuan","@id":"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d"},"headline":"Cholesky Factorization and Elimination Tree","datePublished":"2023-05-03T22:12:46+00:00","dateModified":"2023-11-25T00:03:49+00:00","mainEntityOfPage":{"@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/"},"wordCount":1400,"publisher":{"@id":"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d"},"image":{"@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1","keywords":["Computer Science","Coursework"],"articleSection":["Coursework","UToronto"],"inLanguage":"en-CA"},{"@type":"WebPage","@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/","url":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/","name":"Cholesky Factorization and Elimination Tree ~ rainyuxuan","isPartOf":{"@id":"https:\/\/rainyuxuan.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#primaryimage"},"image":{"@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1","datePublished":"2023-05-03T22:12:46+00:00","dateModified":"2023-11-25T00:03:49+00:00","breadcrumb":{"@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#breadcrumb"},"inLanguage":"en-CA","potentialAction":[{"@type":"ReadAction","target":["https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/"]}]},{"@type":"ImageObject","inLanguage":"en-CA","@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#primaryimage","url":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1","contentUrl":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1","width":1024,"height":1024},{"@type":"BreadcrumbList","@id":"https:\/\/rainyuxuan.com\/posts\/cholesky-factorization-and-elimination-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/rainyuxuan.com\/"},{"@type":"ListItem","position":2,"name":"Cholesky Factorization and Elimination Tree"}]},{"@type":"WebSite","@id":"https:\/\/rainyuxuan.com\/#website","url":"https:\/\/rainyuxuan.com\/","name":"rainyuxuan","description":"My blog and something else \u2728","publisher":{"@id":"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/rainyuxuan.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-CA"},{"@type":["Person","Organization"],"@id":"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d","name":"rainyuxuan","image":{"@type":"ImageObject","inLanguage":"en-CA","@id":"https:\/\/rainyuxuan.com\/#\/schema\/person\/image\/","url":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2022\/01\/64739925_p13.jpg?fit=1149%2C1200&ssl=1","contentUrl":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2022\/01\/64739925_p13.jpg?fit=1149%2C1200&ssl=1","width":1149,"height":1200,"caption":"rainyuxuan"},"logo":{"@id":"https:\/\/rainyuxuan.com\/#\/schema\/person\/image\/"},"sameAs":["https:\/\/www.instagram.com\/yuxuan_27\/","https:\/\/www.linkedin.com\/in\/liuyuxuan2001\/","yu2001xuan@outlook.com"],"url":"https:\/\/rainyuxuan.com\/posts\/author\/yu2001xuan\/"}]}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-2.png?fit=1024%2C1024&ssl=1","_links":{"self":[{"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/posts\/733"}],"collection":[{"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/comments?post=733"}],"version-history":[{"count":5,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/posts\/733\/revisions"}],"predecessor-version":[{"id":948,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/posts\/733\/revisions\/948"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/media\/936"}],"wp:attachment":[{"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/media?parent=733"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/categories?post=733"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/tags?post=733"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}