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":730,"date":"2023-05-03T18:11:02","date_gmt":"2023-05-03T22:11:02","guid":{"rendered":"https:\/\/rainyuxuan.com\/?p=730"},"modified":"2023-12-21T22:05:23","modified_gmt":"2023-12-22T03:05:23","slug":"sparse-linear-systems-and-direct-methods","status":"publish","type":"post","link":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/","title":{"rendered":"Sparse Linear Systems and Direct Methods"},"content":{"rendered":"\n

My study note for my CSC494 course project: Systems for Graphics.
A rough introduction to solving a sparse linear system and related problems. <\/p><\/blockquote><\/figure>\n\n\n\n

Background<\/h2>\n\n\n\n

The project started by investigating the Incremental Potential Contact model for physics-based animation, which is an augmented Newton-type optimizer. We found that the bottleneck of the computation happens at the step of solving for the step-direction, which is a sparse linear solve with a Hessian matrix.<\/p>\n\n\n\n

\\bold{H}\\bold{p}= -\\bold{g}<\/pre><\/div>\n\n\n\n
So my research started with the direct methods for sparse linear systems. These are my study notes that roughly cover some of the basic knowledge and concepts involved in the topic with some expressive figures.<\/p>\n\n\n\n
Great thanks to Behrooz and Prof. Maryam for all their help and support!<\/p>\n\n\n\n
Goal: Solving a sparse linear system<\/h2>\n\n\n\n
The end goal of the problem is to solve for \"\bold{x}\" in a sparse linear system:<\/p>\n\n\n\n
\\bold{Ax}=\\bold{b}<\/pre><\/div>\n\n\n\n
where \"\bold{A}\" is a known sparse matrix, \"\bold{b}\" is a known vector, and \"\bold{x}\" is the UNKNOWN vector.<\/p>\n\n\n\n
The naive method uses the Gaussian Elimination<\/em> to convert \"\bold{A}\" into the row echelon form (as an upper-triangular matrix) and then perform a backward solve<\/em>.<\/p>\n\n\n\n
Another method to solve this linear system is first to perform a matrix factorization<\/em>, to decompose the matrix \"\bold{A}\" into the product of a lower triangular matrix and an upper triangular matrix, and then perform two less costly solves. For our case, \"\bold{A}\" is the Hessian matrix<\/em> in Newton’s Method, which means it is symmetric positive-definite<\/em> (SPD), so that we can apply the Cholesky factorization<\/em><\/strong> to find a lower triangular factor \"\bold{L}\".<\/p>\n\n\n\n
\\bold{A}=\\bold{L}\\bold{L}^\\intercal<\/pre><\/div>\n\n\n\n
And then apply a series of computations:<\/p>\n\n\n\n
\\text{Substitute } \\bold{A}\\bold{x} = \\bold{L} \\bold{L}^\\intercal \\bold{x} = \\bold{b}\n\\\\\n\\text{Let } \\bold{L}^\\intercal \\bold{x} = \\bold{y}\n\\\\\n\\text{Solve } \\bold{L} \\bold{y} = \\bold{b}\n\\\\\n\\text{Solve } \\bold{L}^\\intercal \\bold{x} = \\bold{y}<\/pre><\/div>\n\n\n\n
Solve: algorithm<\/h3>\n\n\n\n
Let’s focus on the problem of \"\bold{L}, whose solution \"\bold{x}\" can be computed iteratively.<\/p>\n\n\n\n
C++<\/span><\/path><\/path><\/svg><\/span>
x <\/span>=<\/span> b<\/span><\/span>\nfor<\/span> j <\/span>=<\/span> <\/span>0<\/span> to n<\/span>-<\/span>1<\/span> <\/span>do<\/span> \/\/ Iterate over b<\/span><\/span>\n  <\/span>if<\/span> <\/span>x<\/span>[<\/span>j<\/span>]<\/span> <\/span>!=<\/span> <\/span>0<\/span>:<\/span><\/span>\n    <\/span>for<\/span> i <\/span>=<\/span> j<\/span>+<\/span>1<\/span> to n<\/span>-<\/span>1<\/span> <\/span>do<\/span>  \/\/ Iterate over rows of L at column j<\/span><\/span>\n      <\/span>x<\/span>[<\/span>i<\/span>]<\/span> <\/span>=<\/span> <\/span>x<\/span>[<\/span>i<\/span>]<\/span> <\/span>-<\/span> <\/span>L<\/span>(<\/span>i<\/span>,<\/span>j<\/span>)<\/span> <\/span>*<\/span> <\/span>x<\/span>[<\/span>j<\/span>]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Sparse<\/h3>\n\n\n\n
For the sparse case, the for-loop at line 4 from the above algorithm can be pruned to only iterate over the columns that the entry j<\/code> is dependent on. See the following figure:<\/p>\n\n\n\n
\"\"
Figure 1<\/figcaption><\/figure>\n\n\n\n
In this example, when we are solving for j = 1<\/code> (the first entry), only the non-zero entries in column j<\/code> of \"\bold{L}\" will affect the later iterations. This gives us the concept of dependency<\/strong><\/em>: the computation of node (column) j<\/code> will only affect a subset of all nodes; only a subset of all nodes will affect the computation of the node j<\/code>.<\/p>\n\n\n\n
The dependency relationship of the nodes in the factor \"\bold{L}\" can be expressed by a Graph \"G_\bold{L}\". We can also visualize it in the factor \"L\", each non-zero entry implies an edge from the entry’s column index to the row index.<\/p>\n\n\n\n
\"\"
Figure 2, (Davis, 2016)<\/figcaption><\/figure>\n\n\n\n
Reach<\/h4>\n\n\n\n
Another way to improve the solve step is to look at the non-zero pattern of \"\bold{b}\" and \"\bold{x}\" and prune line 2 to only iterate over those nodes.<\/p>\n\n\n\n
When the right-hand side \"\bold{b}\" is sparse, the solution \"\bold{x}\" is also sparse. Theorems state that, with the non-zero pattern of columns in \"\bold{L}\", the non-zero pattern of \"\bold{x}\" can also be determined.<\/p>\n\n\n\n
\"\"
Figure 3, (Davis, 2016)<\/figcaption><\/figure>\n\n\n\n
We call the list of the relevant nodes of the non-zero pattern \"B\" of \"\bold{b}\", which is also the non-zero pattern of \"\bold{x}\", the \"Reach_{L}(B)\". The list order of the Reach is a topologic ordering of the nodes, in terms of the order of computation.<\/p>\n\n\n\n
The reach tells: in order to compute a list of nodes, which nodes needed to be computed prior and in what ordering. <\/p>\n\n\n\n
Data structure<\/h2>\n\n\n\n
Let’s start with an easy concept: the data structure for storing the sparse matrix. SuiteSparse stores sparse matrices in a Compressed Sparse Column<\/em><\/strong> (CSC) format. It consists of 3 arrays.<\/p>\n\n\n\n
    \n
  1. p<\/code>: index array of size ncols + 1<\/code>. Storing the beginning index of each column in array i<\/code>.<\/li>\n\n\n\n
  2. i<\/code>: index array of size nzmax<\/code>. Storing the row index of each non-zero. Entries of columns are stored consecutively. Therefore, the array p<\/code> is used to find the beginning of each column.<\/li>\n\n\n\n
  3. x<\/code>: value array of size nzmax<\/code>. Storing the numerical value of each non-zero. Corresponding to the array i<\/code>.<\/li>\n<\/ol>\n\n\n\n
    For the column j<\/code> of a sparse matrix, the row indices of the non-zeros are stored in i[p[j]]<\/code> through i[p[j+1]-1]<\/code>, and the same locations in x<\/code> will store their numerical values.<\/p>\n\n\n\n
    C++<\/span><\/path><\/path><\/svg><\/span>
    \/*<\/span><\/span>\nMatrix:<\/span><\/span>\n  |  1                 |<\/span><\/span>\n  |  1.1  2            |<\/span><\/span>\n  |  1.2       3       |<\/span><\/span>\n  |  1.3  2.3  3.3  4  |<\/span><\/span>\n*\/<\/span><\/span>\n<\/span>\nint<\/span>[] p <\/span>=<\/span>     <\/span>[<\/span>0<\/span>,<\/span>                  <\/span>4<\/span>,<\/span>        <\/span>6<\/span>,<\/span>        <\/span>8<\/span>,<\/span>   <\/span>9<\/span>]<\/span><\/span>\nint<\/span>[] i <\/span>=<\/span>     <\/span>[<\/span>0<\/span>,<\/span>   <\/span>1<\/span>,<\/span>   <\/span>2<\/span>,<\/span>   <\/span>3<\/span>,<\/span>   <\/span>1<\/span>,<\/span>   <\/span>3<\/span>,<\/span>   <\/span>2<\/span>,<\/span>   <\/span>3<\/span>,<\/span>   <\/span>3<\/span>  <\/span>]<\/span><\/span>\ndouble<\/span>[] x <\/span>=<\/span>  <\/span>[<\/span>1.0<\/span>,<\/span> <\/span>1.1<\/span>,<\/span> <\/span>1.2<\/span>,<\/span> <\/span>1.3<\/span>,<\/span> <\/span>2.0<\/span>,<\/span> <\/span>2.3<\/span>,<\/span> <\/span>3.0<\/span>,<\/span> <\/span>3.3<\/span>,<\/span> <\/span>4.0<\/span>]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
    There is also another format called Compressed Sparse Row (CSR), which is basically the same idea as CSC. Interestingly, you may find that the CSC of a matrix is identical to the CSR of its transpose.<\/p>\n\n\n\n
    Anyway, the data structure is not crucial in understanding the concepts in our study.<\/p>\n\n\n\n
    Next Chapter<\/h2>\n\n\n\n
    We have seen that for solving a sparse linear system with a Hessian matrix, we need to know the dependency relations among the columns.<\/p>\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 solving a sparse linear system and related problems. <\/p>\n","protected":false},"author":1,"featured_media":934,"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-730","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coursework","category-uoft","tag-computer-science","tag-coursework"],"yoast_head":"\nSparse Linear Systems and Direct Methods ~ 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\/sparse-linear-systems-and-direct-methods\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Sparse Linear Systems and Direct Methods ~ rainyuxuan\" \/>\n<meta property=\"og:description\" content=\"My study note for my CSC494 course project: Systems for Graphics. A rough introduction to solving a sparse linear system and related problems.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/\" \/>\n<meta property=\"og:site_name\" content=\"rainyuxuan\" \/>\n<meta property=\"article:published_time\" content=\"2023-05-03T22:11:02+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-12-22T03:05:23+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.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=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/\"},\"author\":{\"name\":\"rainyuxuan\",\"@id\":\"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d\"},\"headline\":\"Sparse Linear Systems and Direct Methods\",\"datePublished\":\"2023-05-03T22:11:02+00:00\",\"dateModified\":\"2023-12-22T03:05:23+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/\"},\"wordCount\":863,\"publisher\":{\"@id\":\"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d\"},\"image\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.png?fit=1024%2C1024&ssl=1\",\"keywords\":[\"Computer Science\",\"Coursework\"],\"articleSection\":[\"Coursework\",\"UToronto\"],\"inLanguage\":\"en-CA\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/\",\"url\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/\",\"name\":\"Sparse Linear Systems and Direct Methods ~ rainyuxuan\",\"isPartOf\":{\"@id\":\"https:\/\/rainyuxuan.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.png?fit=1024%2C1024&ssl=1\",\"datePublished\":\"2023-05-03T22:11:02+00:00\",\"dateModified\":\"2023-12-22T03:05:23+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#breadcrumb\"},\"inLanguage\":\"en-CA\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-CA\",\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#primaryimage\",\"url\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.png?fit=1024%2C1024&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.png?fit=1024%2C1024&ssl=1\",\"width\":1024,\"height\":1024},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/rainyuxuan.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Sparse Linear Systems and Direct Methods\"}]},{\"@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":"Sparse Linear Systems and Direct Methods ~ 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\/sparse-linear-systems-and-direct-methods\/","og_locale":"en_US","og_type":"article","og_title":"Sparse Linear Systems and Direct Methods ~ rainyuxuan","og_description":"My study note for my CSC494 course project: Systems for Graphics. A rough introduction to solving a sparse linear system and related problems.","og_url":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/","og_site_name":"rainyuxuan","article_published_time":"2023-05-03T22:11:02+00:00","article_modified_time":"2023-12-22T03:05:23+00:00","og_image":[{"url":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.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":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#article","isPartOf":{"@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/"},"author":{"name":"rainyuxuan","@id":"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d"},"headline":"Sparse Linear Systems and Direct Methods","datePublished":"2023-05-03T22:11:02+00:00","dateModified":"2023-12-22T03:05:23+00:00","mainEntityOfPage":{"@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/"},"wordCount":863,"publisher":{"@id":"https:\/\/rainyuxuan.com\/#\/schema\/person\/ce28dbba3356a4cd768c7cb798b8666d"},"image":{"@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.png?fit=1024%2C1024&ssl=1","keywords":["Computer Science","Coursework"],"articleSection":["Coursework","UToronto"],"inLanguage":"en-CA"},{"@type":"WebPage","@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/","url":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/","name":"Sparse Linear Systems and Direct Methods ~ rainyuxuan","isPartOf":{"@id":"https:\/\/rainyuxuan.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#primaryimage"},"image":{"@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.png?fit=1024%2C1024&ssl=1","datePublished":"2023-05-03T22:11:02+00:00","dateModified":"2023-12-22T03:05:23+00:00","breadcrumb":{"@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#breadcrumb"},"inLanguage":"en-CA","potentialAction":[{"@type":"ReadAction","target":["https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/"]}]},{"@type":"ImageObject","inLanguage":"en-CA","@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#primaryimage","url":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.png?fit=1024%2C1024&ssl=1","contentUrl":"https:\/\/i0.wp.com\/rainyuxuan.com\/wp-content\/uploads\/2023\/05\/BlogImage-494-1-1.png?fit=1024%2C1024&ssl=1","width":1024,"height":1024},{"@type":"BreadcrumbList","@id":"https:\/\/rainyuxuan.com\/posts\/sparse-linear-systems-and-direct-methods\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/rainyuxuan.com\/"},{"@type":"ListItem","position":2,"name":"Sparse Linear Systems and Direct Methods"}]},{"@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-1-1.png?fit=1024%2C1024&ssl=1","_links":{"self":[{"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/posts\/730"}],"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=730"}],"version-history":[{"count":5,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/posts\/730\/revisions"}],"predecessor-version":[{"id":971,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/posts\/730\/revisions\/971"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/media\/934"}],"wp:attachment":[{"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/media?parent=730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/categories?post=730"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/rainyuxuan.com\/wp-json\/wp\/v2\/tags?post=730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}