4 ms·

what book to read to develop these concepts and intuitions with engineering level of math (not proofs)?

dpflan 3y ago
I don't know how proof heavy this course is and it is not specialized on graphs: "Computational Science and Engineering I" -- Gilbert Strang (MIT) https://ocw.mit.edu/courses/18-085-computational-science-and-engineering-i-fall-2008/pages/syllabus/ https://ocw.mit.edu/courses/18-085-computational-science-and...
- algas 3y ago
  The textbook for this course is probably one of the finest Strang ever wrote. It's also worth looking at the original edition of the textbook, which was called "Introduction to Applied Mathematics" and has a much more thorough treatment of the parallels between matrices, graphs, and differential operators, and their use in optimization problems. CSE is much more practical for solving actual scientific computing problems, though, even if I find the layout somewhat less beautiful.
  - dustingetz 3y ago
    oh my, thanks! Ed 1 is the exact book i wanted
    - dpflan 3y ago
      Were you able to find a copy? I found this on archive.org -- https://archive.org/details/introductiontoap0000stra/page/n9/mode/2up https://archive.org/details/introductiontoap0000stra/page/n9...
EsportToys 3y ago
I highly recommend anything in Finite Element Methods, it gives you an immediate grounding to a concrete application. I personally really benefitted a lot in the following YouTube lecture series: https://www.math.colostate.edu/~bangerth/videos.html https://www.math.colostate.edu/~bangerth/videos.html
lukburchard 3y ago
There is a book I would like to recommend, as it was not mentioned. The book "Graph algorithms in the language of linear algebra"[1] gives an overview and intuition of different graph algorithms expressed in linear algebra using semirings. The concept of expressing graphs as adjacency matrices (or incidence matrices) is quite old and was already noted by Koenig[4][5]. I remember the duality was used in some proofs and algorithms while doing my CS degree, e.g., see the Floyd–Warshall algorithm. One advantage of using linear algebra, apart from the beauty of it, is that naturally, vectorization and parallelization strategies become easier to implement. In practice, sparse linear algebra is used to reduce space and computational complexity. This is done by storing the matrices in compressed formats, such as COO/CSR/ELLPack. In HPC, there are multiple frameworks to do distributed sparse linear algebra, and also more graph and GPU focussed frameworks using semirings as the abstraction layer (CombBLAS[2], GraphBLAST[3]). References: [1] Kepner, Jeremy, and John Gilbert, eds. Graph algorithms in the language of linear algebra. Society for Industrial and Applied Mathematics, 2011. [2] Buluç, Aydın, and John R. Gilbert. "The Combinatorial BLAS: Design, implementation, and applications." The International Journal of High Performance Computing Applications 25.4 (2011): 496-509. [3] Yang, Carl, Aydın Buluç, and John D. Owens. "GraphBLAST: A high-performance linear algebra-based graph framework on the GPU." ACM Transactions on Mathematical Software (TOMS) 48.1 (2022): 1-51. [4] D. Konig. Graphen und Matrizen (Graphs and matrices). Matematikai Lapok, 38:116–119, 1931. [5] D. Konig. Theorie der endlichen und unendlichen graphen (Theory of Finite and Infinite Graphs). Leipzig: Akademie Verlag M.B.H. 1936.

I don't know how proof heavy this course is and it is not specialized on graphs: "Computational Science and Engineering I" -- Gilbert Strang (MIT) https://ocw.mit.edu/courses/18-085-computational-science-and-engineering-i-fall-2008/pages/syllabus/ https://ocw.mit.edu/courses/18-085-computational-science-and...

algas 3y ago
The textbook for this course is probably one of the finest Strang ever wrote. It's also worth looking at the original edition of the textbook, which was called "Introduction to Applied Mathematics" and has a much more thorough treatment of the parallels between matrices, graphs, and differential operators, and their use in optimization problems. CSE is much more practical for solving actual scientific computing problems, though, even if I find the layout somewhat less beautiful.
- dustingetz 3y ago
  oh my, thanks! Ed 1 is the exact book i wanted
  - dpflan 3y ago
    Were you able to find a copy? I found this on archive.org -- https://archive.org/details/introductiontoap0000stra/page/n9/mode/2up https://archive.org/details/introductiontoap0000stra/page/n9...

EsportToys 3y ago

I highly recommend anything in Finite Element Methods, it gives you an immediate grounding to a concrete application. I personally really benefitted a lot in the following YouTube lecture series: https://www.math.colostate.edu/~bangerth/videos.html https://www.math.colostate.edu/~bangerth/videos.html

lukburchard 3y ago

There is a book I would like to recommend, as it was not mentioned. The book "Graph algorithms in the language of linear algebra"[1] gives an overview and intuition of different graph algorithms expressed in linear algebra using semirings. The concept of expressing graphs as adjacency matrices (or incidence matrices) is quite old and was already noted by Koenig[4][5]. I remember the duality was used in some proofs and algorithms while doing my CS degree, e.g., see the Floyd–Warshall algorithm. One advantage of using linear algebra, apart from the beauty of it, is that naturally, vectorization and parallelization strategies become easier to implement. In practice, sparse linear algebra is used to reduce space and computational complexity. This is done by storing the matrices in compressed formats, such as COO/CSR/ELLPack. In HPC, there are multiple frameworks to do distributed sparse linear algebra, and also more graph and GPU focussed frameworks using semirings as the abstraction layer (CombBLAS[2], GraphBLAST[3]). References: [1] Kepner, Jeremy, and John Gilbert, eds. Graph algorithms in the language of linear algebra. Society for Industrial and Applied Mathematics, 2011. [2] Buluç, Aydın, and John R. Gilbert. "The Combinatorial BLAS: Design, implementation, and applications." The International Journal of High Performance Computing Applications 25.4 (2011): 496-509. [3] Yang, Carl, Aydın Buluç, and John D. Owens. "GraphBLAST: A high-performance linear algebra-based graph framework on the GPU." ACM Transactions on Mathematical Software (TOMS) 48.1 (2022): 1-51. [4] D. Konig. Graphen und Matrizen (Graphs and matrices). Matematikai Lapok, 38:116–119, 1931. [5] D. Konig. Theorie der endlichen und unendlichen graphen (Theory of Finite and Infinite Graphs). Leipzig: Akademie Verlag M.B.H. 1936.