GSoC 2013 Application Amit: Extensions to Matrix Module - sympy/sympy GitHub Wiki

Extensions to the Matrix Module.

Name : G Amit Jamadagni

University : Birla Institute of Technology and Science- Pilani.

Bio :

I am currently pursuing Masters in Mathematics along with Bachelors in Electrical and Electronics Engineering (M.Sc. Mathematics + B.E.Electrical and Electronics).

Contacts :

Email ID : [email protected]

GitHub : amitjamadagni

IRC : esornep

I have been working on Linux as my primary OS for the past 2 years and have learnt a lot about it.I have been shifting between Ubuntu and Fedora.I like to experiment with various Operating Systems for fun.

I have followed the LFS guide (Linux from Scratch) to compile the kernel (this was from the book) and then added GUI to make a completely independent OS (taking reference from BLFS (Beyond Linux From Scratch)) in summer of 2012 as a self assigned project.I have had the experience of working with various network security tools and have learnt a lot of the network intricacies.I had the opportunity of participating in testing cycles of Ubuntu. I have packaged some .deb packages following the wiki pages on the net and have made some successful packages.

I was introduced to the world of programming through C language. It was a course which was challenging and was exciting at the same time. I loved it and started to search for other languages because I wanted some library support. Being a Math student and my interest in Computation, had propelled me to look into something where the language would speak. And then came Python. I am still in the learning process and have made some great progress in learning it in a short period of time.I have been using gedit and Vim for code editing purposes.

As mentioned above Math forms the basis for physics, and it also being the framework of Physics, I was in search of something which would club both these fields; and coding being my interest, the search was for something like Sympy. For the first time I was impressed by the features it had. Even though it had great amount of math implemented, Physics implementation made me excited.I was doing a course on Quantum Computation and found it had some libraries related to the same.Being an open source enthusiast I always wanted to contribute back.This had everything what I wanted and found it a great platform to start contributing.I have had fun playing around with the integration module of sympy.(Mainly in isympy)


My Contributions to Sympy (Pull Requests)

Merged

1.https://github.com/sympy/sympy/pull/1834

Extension of qapply to the Rotation Operator.

Comments : This was my first exposure to open source and Git and it had everything.Since I was still learning Python there were some elementary mistakes in the start.But as it progressed it had become better not before I met with the obstacle in the test cases.That was a great learning curve and many thanks to all the people who helped me out not only with the code but teaching me how to use Git.

2.https://github.com/sympy/sympy/pull/1900

IntQubit to work on innerproduct.

3.https://github.com/sympy/sympy/pull/1928

Un-merged:

1.https://github.com/sympy/sympy/pull/1945

I have used git in making my contributions to sympy and other projects.I have tried out other version control systems (Mainly in the effort to contribute to projects like Mozbaze).


Project

Aim :

My project would focus on the improving the current matrix module .The aim of the project would be to add additional features like Hankel Matrix, Toeplitz matrix, Circulant matrix ,to mention a few. Further there would an implementation of span, basis and dimension in the matrix space as well as the Polynomial space.Reduction of span and testing the basis using various algorithms available and development of transition matrix and implementation of the kernel of the transformation matrix.More properties relating to Matrix space would be added bringing in the notion of various norms using the currently existing classes.This would include the implementation of Pseudo Inverse of matrix and many properties related to them.It would also add the features of series expansion of matrices and logarithmic and exponential of a matrix.Using the Toeplitz matrix implemented there would be some algorithms which would calculate the eigen values specific to the Toeplitz matrix.

Why this project :

  • Adding of special matrices would add to the robustness of the present matrix module as it would reduce the number of inputs the user has to focus on.

  • The present series implementation of matrices is entirely dependent on the mpmath-module.Current project attempts to bring out an implementation where it would return Symbolic as well as numerical results.

  • Span, Dimensions and Basis implementation is an attempt to make the current implementation of linear algebra more complete.

The current project would deal with the implementation of the following topics :

To the matrix module :

Toeplitz matrix :

Few methods that would be implemented are mentioned for this and would be extended to the other matrices as well.    

(a) The input would be a single row as the matrix is developed from this and the size of the matrix.The output would be a Toeplitz matrix.

>> toeplitz([a,f,g,h,i], [a,b,c,d,e])  

>>[ a, b, c, d, e]
  [ f, a, b, c, d] 
  [ g, f, a, b, c]     
  [ h, g, f, a, b]
  [ i, h, g, f, a]

(b)is_toeplitz :
    Check whether given matrix is Toeplitz or not.

(c)is_Hankel :
    Check whether the Toeplitz matrix is Hankel or not.

(d) Discrete Convolution : 
    Given in the inputs of Toeplitz matrix and given the required co ordinates the convolution of      
    operator and the co ordinates are returned is returned with respect to the given operator.

Hankel Matrix

>> Hankel([a,b,c,d,e], [e,f,g,h,i])

>>[ a, b, c, d, e]
  [ b, c, d, e, f] 
  [ c, d, e, f, g]     
  [ d, e, f, g, h]
  [ e, f, g, h, i]

Other methods as extended for Toeplitz matrix would be extended.

Exchange matrix

>> Exchange(1,2)

>> [0 ,1]
   [1 ,0]

is_centrosymmetric

is_persymmetric

is_bisymmetric

is_projection

Circulant Matrix

>> Circulant([1,2,3])

>> [1 ,2, 3]
   [2 ,3, 1]
   [3, 1, 2]

Pseudo inversion of matrices.(Moore Penrose inverse).

Ar(+) = A' inverse((AA'))

Quasi Diagonal (Page 15)

The matrix inputs on the diagonal would be given.

>> Qausidia(A1,A2,....,An)

>> Dia(A1,A2,....An)

TriDiagonal Matrix

>> Tridiagonal([1,4,3,3],[4,1,4],[3,2,1])

>> [1,4,0,0]
   [3,4,1,0]
   [0,2,3,4]
   [0,0,1,3] 

Pascal Matrix

All the three types would be implemented :

Upper Triangular Pascal Matrix :

>> U5 :

>> [1,1,1,1,1]
   [0,1,2,3,4]
   [0,0,1,3,6]
   [0,0,0,1,4]
   [0,0,0,0,1]

>> L5 :

>> [1,0,0,0,0]
   [1,1,0,0,0]
   [1,2,1,0,0]
   [1,3,3,1,0]
   [1,4,6,4,1]

>> S5 :
   [1,1,1,1,1]
   [1,2,3,4,5]
   [1,3,6,10,15]
   [1,4,10,20,35]
   [1,5,15,35,70]

Vandermonde Matrix

>> V([1,2,3])

>> [1,1,1]
   [1,2,4]
   [1,3,9]

These would add to the current matrices and the implemented Toeplitz and Circulant matrices.

Matrix Norm :

Various matrix norms for any given matrix would be implemented.


(1) Ky - Fan k-norm

    >>Matrix.Norm.Kyfank(A)
    >> maximum of the singular values (Check on whether matrix is normal or not).

(2) Inner Product

    >> row[1,2]*col[1,2]
    >> 5

(3) Outer Product or the Kronecker Product

Sequence of matrices :

 Starting with Commutators of matrix then move onto nested commutators which would be used in Baker–Campbell–Hausdorff formula.

Commutators

Commutator Difference (Symbolic as well as Computational)

>>Commutediff(A,B)
>> AB-BA

>> Commute(A,B)
>> True

Nested Commutators

>> Nested(A,B,3)
>> ( [A,B], [A,[A,B](/sympy/sympy/wiki/A,B],-[A,[A,B) , [B,[A,B]]] )

Series expansion of Matrices

Exponential of matrix : e^X

(a) Taylor Series

e^X = I + X/1! + X/2! + .........

(Depending upon whether the series will converge or not)

The norms implmented would be used to test the convergence.

(b) Solving ODE using numerical integration

Given Xk' = AXk and X(0) = ek 

then xk (t) = e^(tA) ek 

Algorithm :

Reference [5] would be used.

Logarithm of the Matrix

General Pseudo code :

1.Function and the number of terms are taken as input.

2.Depending on the number of terms the coefficients are calculated. (These would be factorials and stored in variables and a for loop would be run to cut down on the variables).

3.Finally these would be clubbed with the terms to display the result.

Before Baker–Campbell–Hausdorff formula is implemented I would like to implement Zassenhaus formula using Nested opertors.This would form the basis for the implementation of the next formula.

Most of the properties mentioned below depend on whether A and B commute or not.So if A and B do not commute for the first property then we use the Baker–Campbell–Hausdorff formula[3].

Method of implementation :

1.Coefficients would be calculated

2.Then these would be integrated into the Baker–Campbell–Hausdorff formula.

Properties : If X and Y commute then e^X * e^Y = e^(X+ Y)

        sin(A+B) = sinAcosB + cosAsinB where A and B commute (This is just an example).

3.Span,Basis and Dimension

Span : Given a span it can be reduced using

    (i) Simplified Span Method
        Span ({5x^3 + 2x^2 + 4x -3, -x^2 + 3x - 7, 2x^3 + 4x^2 - 8x + 5, x^3 + 2x + 5})
        If inputted as 
              >> Span ([5,2,4,-3],[0,-1,3,-7],[2,4,-8,5],[1,0,2,5])
              >> ([1,0,2,0],[1,1,-3,0],[0,0,0,1],[0,0,0,0])

        Taking the coefficients would be a task to work on (sympy.polys.polytools.degree) and recursively calling would be a method here.

        Building back the Span would again construct a polynomial using the reduced span

        (a) Expression of the co ordinates using these span vectors

                >> General co ordinates would be a linear combination of Reduced Span


        (b) This can be extended to matrix space and find the span given any span (Either reduce it 
            or check whether it is already spanning).(That would be a more simplied version compared to polynomials)

Linear Independence.
    (a) Checking for the linear independence of vectors (matrices as well as polynomials) using the 
       Linear Independence Algorithm. (Algorithm referred to Page 205 from the text book on Linear Algebra)

              >> is_independent([3,1,-1] , [-5,-2,2] , [2,2,-1])
              >> True 

    (b) The above procedure can be extended to matrix space 

              >> is_independent[([2,3],[-1,4]),([-1,0],[1,1]),([6,-1],[3,2])]
              >> True

Basis and Dimension :

    (a) The input would be the dimension and the set which is to taken as basis.

    Two conditions are required for the given input to be basis :
        (i) It should span the Space (Verified by the Simplified Span Method)

        (ii)They should be linearly independent (checked by the Linear Independence Algorithm)

    The above rules can be extended to matrix as well as polynomial space.(The input also contains the 
    field)


Implementation of the Co ordinatization method (Finite Ordered Basis)

    Given a finite ordered basis , the aim is to find the co ordinates with respect to these basis.

    By creating a augmented matrix and row reducing(rref) then checking the conditions would allow us to represent co ordinates with respect to the given basis.

Implementation of the Transition Matrix 

    Given the basis to of two systems A and B we can find the transition matrix to move from B to C. Using the Transition Method which creates the augmented matrix.Then the (rref) algorithm should be extended to the augmented matrix to find the transition matrix.(Again this would be a challenge extending)

Implementation of the kernel of a linear transformation.

    (a) Using the kernel method one can find the basis of the kernel of the linear transformation L: Rn --> Rm.

    (b) Using range method to for finding the basis of Rm.

The final implementation if time remains then I would like to start working the implementation of finding eigen values of matrices like Toeplitz using the fast algorithms.

In one of the courses we were dealt with Linear Algebra and it was taken for a semester followed by some real analysis which dealt with properties like metric function where we were introduced to norm.Then we had one more course on Measure again after the abstractness we were dealt with L2 normed spaces. Most of the ideas have been taken from the references and there has been a lot of work going on in improving the efficiency using the special matrices which have been implemented.


Time line :

Community Bonding Period :

The aim of this period would be studying the implementation of the various methods and getting some useful inputs from the mentor as well as the community. This time would also be utilized to revise the various concepts and to move to some greater depths in understanding the algorithms if necessary.

Week 1 - 2 : (1 PR)

(a) Implementation of special matrices , start working on the norms.

(b) Test cases to be implemented.

Week 3 - 4 : (2 PR)

(a) Implementation of the missing norms and laying the foundation for sequence of matrices

(b) Test cases would be implemented.

Week 5 - 6 : (1 PR)

(a) Start working on the series expansion of various mentioned functions(This would be split into two cases)

(b) Test cases would be implemented

MIDTERM EVALUATION :

Week 7 - 10: (2 PR)

(a) Work on the second half the series implementation (mainly focus on Nested Commutators and Baker– Campbell–Hausdorff formula) and start laying the foundation for span, basis and dimension section.

(b) Test cases would be implemented

Week 11 - 13 : (2 PR)

(a) Start working the implementation of topics mentioned under Span , Basis and Dimension.

(b) Test cases would be implemented

Week 14 :

(a) Reviewing the written code and making the changes as required.

(b) Documenting the work.

References :

[1] http://en.wikipedia.org/wiki/Toeplitz_matrix

[2] http://en.wikipedia.org/wiki/Hankel_matrix

[3] http://en.wikipedia.org/wiki/Baker%E2%80%93Campbell%E2%80%93Hausdorff_formula

[4] Elementary Linear Algebra by Andrilli & Hecker.

[5] http://www.ing.unitn.it/~bertolaz/2-teaching/2012-2013/AA-2012-2013-DYSY/lucidi/Exponential.pdf