You're not currently signed in. Sign in »

Tensor Computations (CS 598 EVS) Fall 2020

What Where
Instructor <a href="http://solomonik.cs.illinois.edu/"Edgar Solomonik (solomon2@illinois.edu)
TA Samah Karim (swkarim2@illinois.edu)
Time/place M/W 9:30am-10:45am, (virtual + recorded via zoom, email or see piazza for link to zoom and recordings)
Office Hours After class (10:45-11:15 on zoom) or by appointment (via zoom or other videochat)
Class URL https://relate.cs.illinois.edu/course/cs598evs-f20/
Web forum View Piazza »
Calendar View Calendar »

The course will cover theory, algorithms, and applications of tensor decompositions and tensor networks. The key prerequisite for this material is familiarity with numerical linear algebra topics and algorithmic analysis.

The planned syllabus for the course is below. The major learning objectives for the courser are to establish fluency/inuition of understanding for computations involving tensor contractions and decompositions, to provide a general understanding of theoretical foundations of associated nonlinear optimization problems, to develop a methodology for efficient implementaton of tensor algorithms, and to provide a view of the application landscape of tensor computations.

  • Tensor Algebra

    • characterization of tensors (order, dimensions, symmetry, sparsity)
    • tensor contractions (tensor products, Kronecker products, etc.)
    • tensor notation (matricization, mode-n products, indexing)
    • diagrammatic notation (graphs / Feynman diagrams to represent tensor contractions)

  • Theoretical Fundamentals of Tensor Decompositions

    • Motivating application: bilinear algorithms
    • tensor decomposition rank (CP, Tucker, tensor train)
    • uniqueness, conditioning, and stability (canonical forms)
    • hardness of CP decomposition
    • generalized tensor decomposition
    • tensor eigenvalues

  • Dense Tensor Decomposition Algorithms

    • Motivating application: quantum chemistry
    • CP decomposition algorithms (alternating least squares, Gauss-Newton)
    • Tucker decomposition algorithms (high-order SVD, high-order orthogonal iteration)
    • tensor train SVD

  • Sparse Tensor Decomposition Algorithms

    • Motivating application: recommender systems
    • sparse CP and Tucker decomposition
    • tensor completion algorithms (alternating least squares, coordinate descent, stochastic gradient descent, Gauss-Newton)
    • high-performance implementation of sparse tensor kernels (MTTKRP, TTMc, TTTP) and compressed sparse tensor formats

  • Tensor Network Methods

    • Motivating application: quantum simulation
    • tensor network states (1D/MPS and 2D/PEPS)
    • least-squares and eigenvalue problems with tensor network states
    • alternating minimization techniques (DMRG, TT-ALS)
    • time evolution techniques (Trotterization)

  • Student presentations and lectures on other topics based on student interest

Lectures will be supplemented with short in-class web assignments, which can also be completed asynchronously. Three short homework assignments are planned to test understanding, which can be completed individually or in small groups. Students have the choice of giving a presentation or preparing a report on a research project or review. In-class assignments, homeworks, and the presentation/report will each be worth 1/3 of the grade.

Mini-Homeworks

Homework 1: Preconditioning via Low-Rank Approximation »

Homework 2: Accelerating CP-ALS using Tucker »

Homework 3: Review of Tensor Computations »

Quizzes (in-class activities)

Quiz 1: Interest Survey »

Quiz 2: Computing the Maximum Ritz Value »

Quiz 3: Low Rank Approximation: Randomized SVD vs Krylov Subspace Methods »

Quiz 4: Gauss-Newton Method »

Quiz 5: Kronecker Product as a Tensor Operation »

Quiz 6: Converting a CP Decomposition to a Tucker Decomposition »

Quiz 7: HOSVD and TTSVD »

Quiz 8: Bilinear Algorithms for Convolution »

Quiz 9: Bilinear Algorithm for Multiplication of a Symmetric Matrix and a Vector »

Quiz 10: Tensor Contraction with Group Symmetry »

Quiz 11: Alternating Least Squares for CP Decomposition »

Quiz 12: Dimension Trees for CP ALS »

Quiz 13: Gauss-Newton Method for CP Decomposition »

Quiz 14: Sparse Tensor times Matrix using CSF Format »

Quiz 15: Nonnegative Tensor Factorization »

Quiz 16: Imaginary Time Evolution »

Quiz 17: Density Matrix Renormalization Group (DMRG) »

Quiz 18: Tensor Network Canonical Forms »

Quiz 19: Computing Eigenvalues of a Symmetric Tensor »

Student Presentation Activity: Symmetric CP Decomposition »

Project Report »

Course Outline

  • Course Overview

  • Matrix Computations Background
    • Lecture Notes 
      •   <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/02_lecture.mp4">Lecture 2 Recording (Aug 26, 66 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:02-code-ritz">Quiz 2: Computing the Maximum Ritz Value</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/03_part1_lecture.mp4">Lecture 3 Recording (Aug 31, part 1, 32 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/03_part2_lecture.mp4">Lecture 3 Recording (Aug 31, part 2, 15 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:03-svd-krylov">Quiz 3: Low Rank Approximation: Randomized SVD vs Krylov Subspace Methods</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/04_part1_lecture.mp4">Lecture 4 Recording (Sep 2, part 1, 43 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/04_part2_lecture.mp4">Lecture 4 Recording (Sep 2, part 2, 15 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/05_lecture.mp4">Lecture 5 Recording (Sep 9, 58 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/06_part1_lecture.mp4">Lecture 6 Recording (Sep 14, part 1, 12 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/06_part2_lecture.mp4">Lecture 6 Recording (Sep 14, part 2, 15 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:04-gn-mat">Quiz 4: Gauss-Newton Method</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/07_lecture.mp4">Lecture 7 Recording (Sep 16, starts at 9:39, 60 minutes)</a>
  </li>
</ul>

    • Basics of Tensor Computations
      • Lecture Notes 
        •   <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/08_lecture.mp4">Lecture 8 Recording (Sep 21, 73 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:05-kron">Quiz 5: Kronecker Product as a Tensor Operation</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/09_lecture.mp4">Lecture 9 Recording (Sep 23, 73 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:06-cp-tucker">Quiz 6: Converting a CP Decomposition to a Tucker Decomposition</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/10_lecture.mp4">Lecture 10 Recording (Sep 28, 74 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:07-hosvd">Quiz 7: HOSVD and TTSVD</a>
  </li>
</ul>

      • Bilinear Algorithms
        • Lecture Notes 
          •   <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/11_lecture.mp4">Lecture 11 Recording (Sep 30, 77 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:08-toom-cook">Quiz 8: Bilinear Algorithms for Convolution</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/12_lecture.mp4">Lecture 12 Recording (Oct 5, 73 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:09-sym-mat-vec">Quiz 9: Bilinear Algorithm for Multiplication of a Symmetric Matrix and a Vector</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/13_lecture.mp4">Lecture 13 Recording (Oct 7, 78 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:10-group-sym">Quiz 10: Tensor Contraction with Group Symmetry</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/14_lecture.mp4">Lecture 14 Recording (Oct 12, 79 minutes)</a>
  </li>
</ul>

        • Tensor Decomposition
          • Lecture Notes 
            •   <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/15_lecture.mp4">Lecture 15 Recording (Oct 14, 78 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:11-cp-als">Quiz 11: Alternating Least Squares for CP Decomposition</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/16_lecture.mp4">Lecture 16 Recording (Oct 19, 77 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:12-cp-als-msdt">Quiz 12: Dimension Trees for CP ALS</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/17_lecture.mp4">Lecture 17 Recording (Oct 26, 78 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:13-cp-gn">Quiz 13: Gauss-Newton Method for CP Decomposition</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/18_lecture.mp4">Lecture 18 Recording (Oct 28, 75 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:14-csf-ttm">Quiz 14: Sparse Tensor times Matrix using CSF Format</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/19_lecture.mp4">Lecture 19 Recording (Nov 1, 73 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:15-ntf">Quiz 15: Nonnegative Tensor Factorization</a>
  </li>
</ul>

          • Tensor Networks
            • Lecture Notes 
              •   <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/20_lecture.mp4">Lecture 20 Recording (Nov 3, 73 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:16-ite">Quiz 16: Imaginary Time Evolution</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/21_lecture.mp4">Lecture 21 Recording (Nov 9, 79 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:17-dmrg">Quiz 17: Density Matrix Renormalization Group</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/22_lecture.mp4">Lecture 22 Recording (Nov 11, 78 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:18-canon">Quiz 18: Tensor Network Canonical Forms</a>
  </li>
</ul>

            • Tensor Eigenvalues
              • Lecture Notes 
                •   <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/23_lecture.mp4">Lecture 23 Recording (Nov 16, 66 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-film"}'>
    <a href="http://solomonik.cs.illinois.edu/teaching/cs598_fall2020/24_lecture.mp4">Lecture 24 Recording (Nov 18, 76 minutes)</a>
  </li>
  <li data-jstree='{"icon": "fa fa-check-circle"}'>
    <a href="flow:19-shopm">Quiz 19: Computing Eigenvalues of a Symmetric Tensor</a>
  </li>
</ul>

Related Courses

CS 598 EVS: Provably Efficient Algorithms for Numerical and Combinatorial Problems, Spring '20

CS 450: Numerical Analysis, Fall '18

Related Texts

  • Matrix Computations Gene Golub and Charles Van Loan, 4th Edition, The John's Hopkins University Press, 2013.
  • Tensor Decompositions and Applications T.G. Kolda and B.W. Bader, SIAM Review, 2009.
  • A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States R. Orus, Annals of Physics, 2014.

Python Help

We will be using Python with the libraries numpy, scipy and matplotlib for in-class work and assignments.

Python Workshop Material

Numpy Help

Statement and Support Resources on Mental Health

Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.

Counseling Center: 217-333-3704, 610 East John Street Champaign, IL 61820

McKinley Health Center:217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801