You're not currently signed in. Sign in »

Tensor Computations (CS 598 EVS) Spring 2022

What Where
Instructor <a href="http://solomonik.cs.illinois.edu/"Edgar Solomonik (solomon2@illinois.edu)
TA Samah Karim (swkarim2@illinois.edu)
Time/place Tu/Thu 9:30am-10:45am, (hybrid from 1302 Siebel from 1/25), Zoom link: https://illinois.zoom.us/j/83363404302 (email Edgar for password)
Office Hours Edgar: Thu 10:45-11:45, 4229 Siebel Center
Lecture Recordings https://mediaspace.illinois.edu/channel/CS+598+EVS%3A+Tensor+Computations_+Spring+2022/243978282
Discussion / Announcements https://chat.labpna.net/cs598evs-sp22/channels/town-square
Class URL https://relate.cs.illinois.edu/course/cs598evs-s22/

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/intuition 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 implementation of tensor algorithms, and to provide a view of the application landscape of tensor computations.

  • Review of Topics in Numerical Analysis

    • matrix factorizations
    • eigenvalues, singular values, and matrix conditioning
    • iterative methods and preconditioning
    • quadratic and nonlinear optimization methods
    • graphs and sparse matrices

  • 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)

  • Tensor Decompositions

    • tensor decompositions and rank (CP, Tucker, tensor train)
    • uniqueness and conditioning
    • complexity of exact and approximate decompositions
    • optimization algorithms for tensor decompositions
    • high-performance implementation of sparse tensor kernels
    • tensor completion and generalized tensor decomposition
    • bilinear algorithms and other applications

  • Tensor Networks

    • 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)
    • canonical forms and environments
    • applications in quantum simulation

  • Tensor Eigenvalues

    • variational perspective on eigenvalues and singular values
    • Perron-Frobenius theorem for tensor eigenvectors and other properties
    • algorithms for computing tensor eigenvectors
    • application to hypergraph partitioning

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.

The homeworks and in-class activities will be posted here on a rolling basis. See the webpage for the 2020 offering to get an idea of the assignments.

Proposal and Project

Project Proposal »

Project/Presentation »

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)

Please complete these within 2 weeks of the lecture in which they are covered (or by Feb 15th for early quizzes). Active sessions will be expired sometime after that unless an extension is requested.

Quiz 1: Interest Survey »

Quiz 2: Computing the Maximum Ritz Value »

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

Quiz 4: Finding Minimum of Quadratic Function in a Subspace »

Quiz 5: Graph Partitioning via the Fiedler Vector »

Quiz 6: Gauss-Newton Method »

Quiz 7: Interior Point Methods for Quadratic Programming »

Quiz 8: Kronecker Product as a Tensor Operation »

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

Quiz 10: HOSVD and TTSVD »

Quiz 11: Bilinear Algorithms for Convolution »

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

Quiz 13: Alternating Least Squares for CP Decomposition »

Quiz 14: Dimension Trees for CP ALS »

Quiz 15: Gauss-Newton Method for CP Decomposition »

Quiz 16: Sparse Tensor times Matrix using CSF Format »

Quiz 17: Nonnegative Tensor Factorization »

Quiz 18: Imaginary Time Evolution »

Quiz 19: Tensor Network Canonical Forms »

Quiz 20: Density Matrix Renormalization Group (DMRG) »

Quiz 21: Computing Eigenvalues of a Symmetric Tensor »

Quiz 22: Computing an Exact Low Rank CP Decomposition »

Course Outline

  • Course Overview
    • Lecture Notes 
        </li>
</ul>

    • Matrix Computations Background
      • Lecture Notes
        • Live scribbles 1 
          •       <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/01-sc2.pdf">Live scribbles 2</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/01-sc3.pdf">Live scribbles 3</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/01-sc4.pdf">Live scribbles 4</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/01-sc5.pdf">Live scribbles 5</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/01-sc6.pdf">Live scribbles 6</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/01-sc7.pdf">Live scribbles 7</a>
      </li>
    </ul>
  </li>
</ul>

        • Basics of Tensor Computations
          • Lecture Notes
            • Live scribbles 1 
              •       <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/02-sc2.pdf">Live scribbles 2</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/02-sc3.pdf">Live scribbles 3</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/02-sc4.pdf">Live scribbles 4</a>
      </li>
    </ul>
  </li>
</ul>

            • Bilinear Algorithms
              • Lecture Notes
                • Live scribbles 1 
                  •       <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/03-sc2.pdf">Live scribbles 2</a>
      </li>
    </ul>
  </li>
</ul>

                • Tensor Decomposition
                  • Lecture Notes
                    • Live scribbles 1 
                      •       <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-sc2.pdf">Live scribbles 2</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-sc3.pdf">Live scribbles 3</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-sc4.pdf">Live scribbles 4</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-sc5.pdf">Live scribbles 5</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-sc6.pdf">Live scribbles 6</a>
      </li>
      <li data-jstree='{"icon": "fa fa-book"}'>
        <a href="repocur:lectures/scribbles/04-sc7.pdf">Live scribbles 7</a>
      </li>
    </ul>
  </li>
</ul>

                    • Tensor Networks

Related Courses

CS 598 EVS: Tensor Computations, Fall '20

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

CS 450: Numerical Analysis, Spring '21

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.
  • Numerical Linear Algebra N. Trefethen and D. Bau, SIAM 1997.
  • Applied Numerical Linear Algebra J. Demmel, SIAM 1997.
  • Scientific Computing: An Introductory Survey M.T. Heath, SIAM 1997.

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