Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Linear Algebra and Optimisation

Introductory Lecture

N. Anil
BITS Pilani, Hyderabad Campus
anil@hyderabad.bits-pilani.ac.in

July 27, 2024

1 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Scope of the Course

This is an introductory course on

• Linear Algebra

• Optimisation

2 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Introduction to Linear Algebra

What is a linear equation ?

An equation involving one or more variables with constant coefficients

Examples: x = 4, x + y = 1, 2x + y − 3z = 5, etc.

3 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Introduction to Linear Algebra

What is a linear equation ?

An equation involving one or more variables with constant coefficients

Examples: x = 4, x + y = 1, 2x + y − 3z = 5, etc.

A general form :

a1 x1 + a2 x2 + a3 x3 + · · · + an xn = b

3 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Introduction to Linear Algebra

What is a system of linear equations ?

Several linear equations involving the same variables

(
x+y =1
Examples:
x−y =3
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Introduction to Linear Algebra

What is a system of linear equations ?

Several linear equations involving the same variables


(  x+ y+ z =1

x+y =1 
Examples: , x − y + 3z = 3
x−y =3 
2x + 3y − 4z = 5

4 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Introduction to Linear Algebra

System of linear equations : General form



 a11 x1 + a12 x2 + a13 x3 + · · · + a1n xn = b1

a21 x1 + a22 x2 + a23 x3 + · · · + a2n xn = b2


.. .. ..



 . . .


am1 x1 + am2 x2 + am3 x3 + · · · + amn xn = bm

5 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Types of Linear System of Equations

A given system of equations can be classified into the following three groups:

• Determined system: Number of equations is same as the number of variables.

• Over-determined system: Number of equations is more than the number of

variables.

• Under-determined system: Number of equations is less than the number of

variables.

6 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

System of Equations: Existence and Uniqueness of Solution

Given a system of equations, we have the following possibilities

• Solution exists and it is unique.

7 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

System of Equations: Existence and Uniqueness of Solution

Given a system of equations, we have the following possibilities

(
x+y =1
• Solution exists and it is unique. Example:
x−y =3

• Solution exists but there are infinitely many.

7 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

System of Equations: Existence and Uniqueness of Solution

Given a system of equations, we have the following possibilities

(
x+y =1
• Solution exists and it is unique. Example:
x−y =3

(
x+ y =2
• Solution exists but there are infinitely many.
2x + 2y = 4

• No solution.

7 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

System of Equations: Existence and Uniqueness of Solution

Given a system of equations, we have the following possibilities

(
x+y =1
• Solution exists and it is unique. Example:
x−y =3

(
x+ y =2
• Solution exists but there are infinitely many.
2x + 2y = 4

(
x+y =1
• No solution. Example :
x+y =3

The essence of linear algebra is to investigate the circumstances under which these
scenarios are possible

7 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

System of equations : Matrix form

What is the role of Vectors/Matrices in linear algebra ?

8 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

System of equations : Matrix form

What is the role of Vectors/Matrices in linear algebra ?

(
x+y =1
Consider the linear system:
x−y =3

Let us define " # " # " #

1 1 x 1
A= , x= and b =
1 −1 y 3
The given system can then be written in the compact form as

Ax = b

8 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

System of equations : Matrix form

Another example : 
x + y + z = 1


x−y+z =2 (1)


x+y−z =3


Let us define
     
1 1 1 x 1
A = 1 −1 1  , x = y  and b = 2
     

1 1 −1 z 3

Equation (1) can be written as

Ax = b (2)

The solution of the linear system is nothing but the solution of Ax = b

9 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Solution techniques for Ax = b: Well-known approach

• Solution is given by x = A−1 b

• The solution exists provided A−1 exists

• A−1 = Adj(A)/Det(A)

• A−1 requires the determinant of A

• For large dimensions, computing the determinant is expensive

• Even computer algorithms do not prefer it !

• Need efficient algorithms for the solution of Ax = b !!

10 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Solution techniques for Ax = b: Alternative approaches

• Consider the following linear system

(
x+y =1
x−y =3

• We can write it as " #" # " #

1 1 x 1
=
1 −1 y 3

• Can we get the following through some manipulations (what are they ?)
" #" # " #
1 1 x 1
=
0 −2 y 2

• Now it is easy to find the solution !

• We Transformed the given matrix to a row echelon form. The first part of the
course deals with some of these basic techniques (Gauss elimination, Gauss
Jordan)

11 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Solution techniques for Ax = b: Abstract Concepts

Consider the same invertible system

" #" # " #
1 1 x 1
=
1 −1 y 3

• Replace a column vector in the coefficient matrix with any arbitrary vector

• What happens to the solution. Does it exist ?

• Does that vector has any relation with the existing ones. Is it dependent or
independent (what does this mean ??)

• This leads us to the concept of linear independence/dependence of vectors

• The set of vectors with some special properties is a vector space

12 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Solution techniques for Ax = b: Abstract Concepts

Consider the same invertible system

" #" # " #
1 1 x 1
=
1 −1 y 3

• We generalise: What are those vectors for which the solution exists !

• The concept of vector spaces and related topics precisely deal with it

• What about the eigenvalues and eigenvectors ? Do they say anything about the
nature of the solution or the column vectors ?

• Does the rank of a matrix say anything about the solution ?

• What is the role the coefficient matrix ?

• These abstract concepts give an insight into the nature of the linear system

13 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Linear Algebra: Role of High Performance Computing

• Solving the linear system by hand is limited to 3 or 4 equations

• Beyond this, use of computers is inevitable

• Small number of equations can be solved on a laptop/desktop

• Large number of equations can be solved on a workstation

• Very large number of equations : Cluster

• Many practical applications involve linear systems with billions of equations.

Need Terascale/Petascale/Hexascale Super Computers !!

Need more sophisticated algorithms that are robust, computationally efficient and can
be applied to very large systems with much ease

14 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Linear Algebra: Role of High Performance Computing

Computer implementation of algorithms in linear algebra:

• Traditional codes are based on Fortran, C, C++

• With continuous evolution in computer hardware, porting these codes on modern
HPC platforms is a challenging task
• Code developer needs to tune it frequently
• To circumvent this problem, we can use Julia or Regent
• They are architecture independent, ease code maintenance, code readability
• Regent results in Implicitly parallel solver
• Suits to hybrid parallel codes (CPUs+GPUs)

15 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Linear Algebra: Some of the Application Areas

• Computational biology/chemisty/physics

• Computer graphics, data mining, digital signal processing

• Audio, video and image processing

• Computational Fluid Dynamics

• Computational Structural Mechanics

• Computational Quantum Mechanics

• Computational Finance

• Other related Computational Engineering Science (CES) problems

16 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Numerical Linear Algebra

Numerical implementation of algorithms in linear algebra:

• Numerical algorithms for the solution of linear systems

• To perform matrix operations, inverse, determinant, eigenvalues, etc.

• Standard software library : LAPACK, LAPACK++

• LAPACK uses BLAS (Basic Linear Algebra Subprograms) libraries

• Matlab, Mathematica, Maple use LAPACK libraries

• MATLAB (Matrix Laboratory) is a fourth generation programming language.

Introduced by Cleve Moler from Univ. New Mexico.

• Apps: Wolfram

• PETSc (Portable, Extensible Toolkit for Scientific Computation)

17 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Course Description - Linear Algebra

The linear algebra part has five modules:

• Matrices, System of equations, determinants and inverse of a matrix

• Vector spaces and Linear transformations

• Eigenvalues and eigenvectors

• Numerical Linear Algebra: Gauss elimination and iterative methods for solving
linear systems

• Matrix eigenvalue problems and power method for eigenvalue

18 / 19
Scope of the Course Introduction to Linear Algebra Topics to be covered in Linear Algebra References

Text and Reference books

• Erwin Kreyszig, Advanced Engineering Mathematics, Wiley India, 10th

Edition 2011.

• B. Dubey, Introductory Linear Algebra, Asian Books Pvt Ltd, 2007.

• K Hoffman and R Kunze, Linear Algebra, Pearson Education, 2nd Edition, 2005.

• Elementary linear algebra - S. Andrilli and David Hecker.

• Introduction to linear algebra - G. Strang.

19 / 19