You're not currently signed in. Sign in »

CS 554 / CSE 512: Parallel Numerical Algorithms (Fall 2023)

What Where
Time Wed/Fri 11:00-12:15
Location 1302 Siebel
Instructor Edgar Solomonik (office: 4229 Siebel, email: solomon2@illinois.edu)
Instructor Office Hours Fridays 2:30-3:30pm (4229 Siebel)
TA Alexey Voronin (email: voronin2@illinois.edu)
TA Office Hours Tuesdays 2-3pm (virtual/zoom: see piazza for a link)
Class URL https://relate.cs.illinois.edu/course/cs554-f23/
Class recordings View MediaSpace »
Web forum View Piazza »

Brief Course Description

Numerical algorithms for parallel computers: parallel algorithms in numerical linear algebra (dense and sparse solvers for linear systems and the algebraic eigenvalue problem), numerical handling of ordinary and partial differential equations, and numerical optimization techniques.

Assignments

Homework 1 (due September 6th) »

Homework 2 (due September 27th) »

Project Proposal (due Oct 11) »

Homework 3 (due Nov 17th) »

Project Report (due Dec 13th) »

Quizzes

Due a week after the start of each lecture, posted prior to lecture, covered in class.

Quiz 1: Parallel Architectures »

Quiz 2: Network Topologies and Collective Communication »

Quiz 3: Collective Communication and Parallel Algorithm Design »

Quiz 4: Parallel Algorithm Design »

Quiz 5: Parallel Programming Languages »

Quiz 6: Analysis of Parallel Algorithms »

Quiz 7: Efficiency and Scalability for Vector and Matrix Products »

Quiz 8: Parallel Matrix Multiplication and LU Factorization »

Quiz 9: LU Factorization and Triangular Solve »

Quiz 10: Triangular Solve and Sparse Matrix Products »

Quiz 11: Sparse Triangular Solve and Elimination »

Quiz 12: Parallel Sparse Cholesky »

Quiz 13: Parallel Sparse Iterative Methods »

Quiz 14: Preconditioned Iterative Methods and QR Factorization »

Quiz 15: Givens Rotations for QR and Parallel Eigenvalue Computation »

Quiz 16: Parallel Eigenvalue Computation and Fourier Transform »

Quiz 19: Low Rank Approximation and Randomized Algorithms »

Quiz 20: HSS Matrices and Nonlinear Optimization »

Quiz 21: Matrix Completion and ODE IVPs »

Quiz 22: Solvers for Numerical PDEs »

Quiz 23: Molecular Dynamics »

Quiz 24: Quantum Chemistry »

Quiz 25: Tensor Decompositions »

Course organization

Virtual and physical participation for all components the course will be made possible. Late enrollment/registration is also possible (immediate participation is welcome if registration is anticpated).

Grading: 30% project, 25% homework, 18% midterm (in class, Oct 20), 18% final (in class, Dec 6th), 9% quizzes may be subject to upwards curve

Projects: Submit initial proposal by Oct 11, revisions may be requested and will be due Oct 27. Projects related to ongoing investigations or overlapping with other courses are encouraged, so long as they have some component related to this course. A project poster session will be held on Dec 1st and reports are due on Dec 13th.

Slides and notes are based on the Fall 2015 slides by Michael T. Heath. Resources relevant to the course are available also on the old course webpage by Prof. Heath. See also the previous course webpage.

Course Outline

  • Chapter 1: Parallel Computing

  • Chapter 2: Parallel Thinking
    • Notes 
      •   <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Parallel Algorithm Design
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_02.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Parallel Programming
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_03.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Parallel Perfromance
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_04.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
</ul>

    • Chapter 3: Dense Linear Systems
      • Vector and Matrix Products
        • Lecture Slides 
          •     </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    LU Factorization
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_06.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Triangular Linear Systems
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_07.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
</ul>

        • Chapter 4: Sparse Linear Systems
          • Direct Methods
            • Lecture Slides 
              •     </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Tridiagonal and Banded Matrices
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_09.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Sparse Iterative Methods
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_10.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
</ul>

            • Chapter 5: Eigenvalue Problems
              • QR Factorization
                • Lecture Slides 
                  •     </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Eigenvalue Computation
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_12.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
</ul>

                • Chapter 6: Matrix Models
                  • Fast Fourier Transform
                    • Lecture Slides 
                      •     </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Low Rank Approximation
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_14.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Numerical Optimization
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_15.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
</ul>

                    • Chapter 7: Differential Equations
                      • Ordinary Differential Equations
                        • Lecture Slides 
                          •     </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Partial Differential Equations
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_17.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Particle Methods
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_18.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Electronic Structure Calculations
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_19.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
  <li data-jstree='{"icon": "fa fa-puzzle-piece", "opened": true}'>
    Tensor Analysis
    <ul>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:slides/slides_20.pdf">Lecture Slides</a>
      </li>
    </ul>
  </li>
</ul>