GSoC 2017 Application Aditya Chetan: Implementing a linear algebra module

Aditya Chetan edited this page Apr 3, 2017 · 2 revisions
Clone this wiki locally

Personal Details

Heading Details
Name Aditya Chetan
University Indraprastha Institute of Information Technology, New Delhi (IIIT-D)
Major Computer Science and Applied Mathematics
E-Mail achetan40@gmail.com
GitHub achetan40
Github Profile https://github.com/achetan40
Timezone IST (UTC + 5:30)

Bio

I started coding last year, Python being my first language. I honestly feel that for someone who has started coding, there can’t be any language better than Python. The simple syntax and the “batteries-included” approach followed by the platform helped me greatly in getting interested in coding. Not only this, but it was through learning about Python over the internet that I came to know about open-source projects. I love Python for a multitude of reasons, ranging right from its easy syntax to its widespread open-source community and support. But the feature that I like the most is how easy it is to build almost anything in Python. Things like an HTTP Server that take almost months to code in languages like C, take just a single line in Python! This “batteries-included” approach of Python draws me to it.

I have worked on a few small projects of my own. I have worked on projects ranging from game development on Unity to building IoT solutions and writing Python scripts to work around various problems, from crawling the web to reading serial data received from a microcontroller.

SymPy is one great example for me to justify why I love Python. Being an ardent Math lover, I love to submit my Maths class assignments in Latex, since it is a beautiful way to capture mathematical expressions. However, most TeX compilers I found were unstable and had a tendency to crash and that would unnecessarily delay my work. I was looking for a suitable replacement when, while browsing the web, I came across SymPy. The way it has captured the symbolic representation of mathematics into a language as easy and as platform-independent as Python is incredible. However, my favorite feature of SymPy is how it can shrink complex equations and methods into a few lines of Python code. For example, the Gram-Schmidt process in Linear Algebra used to take me a lot of time to complete on paper. SymPy, on the other hand, shrinks down the whole process to just a few lines of code, something I did not imagine possible. Although I am a beginner when it comes to using Git, having learned it just a few months ago, I have used it in other projects that I have worked on and am reasonably comfortable with it.

Proposal

Sympy, through its sympy.matrices module implements most of the functions of Linear Algebra. However, as a whole, it does not implement abstract concepts of Linear Algebra such as vector spaces, subspaces, and fields. I want to work on this deficiency by implementing a module which works on improving the existing matrix-based functions and covers abstract concepts of linear algebra as well, such as vector spaces and subspaces.

For example, consider the vector space of m x n matrices. We can have a class in Python that creates such a vector space. An object of this class would require various parameters to be passed to it, such as the dimensions of the matrix, the underlying field of scalars, the elements of the matrix itself. Here is a pseudo code of the constructor of the class that I wish to implement:

class vectorSpace:
    """
    Attributes:
        (m,n) : Dimensions of the matrices
        F     : Underlying field of scalars
    """
    def __init__(m,n,F):
        self.m = m
        self.n = n
        self.F = F
        
        # check to ensure closure under vector addition
        checkifAddsatisfied()
        
        # check to ensure closure under scalar multiplication
        checkifMulsatisfied()
        
        .
        .
        .
        
        # other checks that may be required 

Other tests include checking for commutativity, associativity and existence additive inverse.

This of course, is a very basic implementation, since a vector space may also be defined on a basis that may have been provided. But of course, we can add another constructor for it by making use of overloaded constructors.

However, a vector space cannot be complete without us defining its laws of addition and scalar multiplication. For example, even a space that follows modular addition and scalar multiplication qualifies to be a vector space.

Similarly, I propose to implement a class for subspaces. Creating an object of this class will, however, require a check to ensure that a previous vector space object has been defined since the subspace will inherit its methods of addition and subtraction from its parent vector space. The pseudo code will look something like this:

class subspace:
    """
    Attributes:
        V   :  parent vector space
        def :  definition of the elements in it
    """
    def __init__(V,def):
        self.V = V
        self.def = def
        
        # check to ensure closure under vector addition
        checkifAddsatisfied()
        
        # check to ensure closure under scalar multiplication
        checkifMulsatisfied()

In the case of subspaces, just two tests are necessary, since that is how subspaces are defined. Again, this is just an example of how I think subspaces can be defined. There are, of course, other ways to define them, such as in terms of a basis.

Once, this has been done, I plan to work on porting methods related to Linear Algebra from the sympy.matrices module, as well as implement other methods that might be necessary. For example, the sympy.matrix module has a diagonalize method that returns a tuple containing the diagonalized matrix. I plan to do the same thing in my own module, but this time include a function that can also check if the matrix/vector is diagonalizable or not. I also plan to re-implement functions that related to eigenvalues and eigenvectors as they too are indispensable parts of linear algebra.

After this, I plan to implement the concepts of inner product spaces and orthogonal spaces in the module. inner product and orthogonality into the module. These products will be relatively easy to implement. What would be more challenging would be is to check whether an inner product exists for a given vector space. A pseudo code for the same would look something like this:

def hasInnerProduct(vectorSpace V):

    for any vectors in V make the following checks:
        
        # u, v, w are vectors in V
        # c is a scalar belonging to the field of V
        
        <u,v> = <v,u>
        <u+v,w> = <u,w> + <v,w> 
        <cu,v> = c<u,v>  
        <u,u> > = 0 && equality holds iff u = 0

Building upon this I also plan to implement the concepts of orthogonality and orthogonal spaces. Again, with orthogonality as well, there would be a need to provide a check on whether the vector space has an inner product in the first place since orthogonality means that the inner product of the operands is zero.

Open for discussion

This is a list of features that I would like to include in this project but I need to have a more thorough discussion about.

  • A function to recognize, if not output directly the span or basis of a vector space or subspace. What I want to do is enable the user to input a vector space and get the span or basis as the output or return a boolean response to whether the given set is a span or basis of the vector space.
  • I would prefer not to entirely re-implement the functions in the sympy.matrix module but work out a way to reuse the matrix objects as objects within my own class, or typecast them as objects of my own class.
  • Implementing linear transformations for vector spaces whose basis has not been provided by the user.

I want to work on this idea in particular, as having done a course in Linear Algebra, and also used several platforms that inculcate mathematical coding, they still haven’t dealt with vector spaces as a separate class of objects. Basically, what I want to do is re-implement the functions related to Linear Algebra but this time as a part of a vector space-centric module.

I have done a course in Linear Algebra that covered topics like vector spaces, subspaces, spans, bases, rank, inner product spaces, coordinate systems, linear transformations, quadratic forms, and SVD. The course was based on a standard international text in Linear Algebra and hence my foundational and structural knowledge in Linear Algebra is strong. I have also taken courses in Python and am quite comfortable with the language.

Timeline

Community Bonding Period

I will use this time to familiarize myself with the existing code base and chalk out the specifics of my idea by discussing it with my mentors and the rest of the SymPy community. I will also work on possible ways to implement the ideas mentioned in the "Open for discussion" subsection. I have already used SymPy before and am pretty confident with using Python, so I can use more of this time to build up on my idea. I also plan to revisit my concepts in Linear Algebra so that I can integrate them into SymPy in the best possible way.

Week 1 (May 30 - June 7)

I plan to read up about alternate implementations of vector spaces on other platforms. This will help me decide where do they lack and how I can make my own implementation better.

Week 2 (June 8 - June 15)

I will start coding based on the findings that I make during Week 1. I think that this part of the project should be pretty straightforward and easy to code, so I will proceed to implement the portion that deals with subspaces. I plan to submit at least one PR this week, complete with the implementation of the vector space class. The tests and documentation for the same shall be pushed along with the code as well.

Week 3 (June 16 - June 24)

I plan to finish my work on implementing subspaces and study the matrix module to single out what all the methods that I plan to reimplement in my own module. As of now, I am yet to decide how and which all functions I will be implementing. I will read up about what is necessary and begin my implementation. Again, I plan to submit a PR at least once every two weeks to avoid much work in resolving conflicts in the end. The tests and documentations for the modifications made till this period shall be pushed in this PR itself.

Milestone 1 : Finish any unfinished work till this period for first evaluations by the mentor

Week 4 and Week 5 (June 27 - July 10)

I plan to start off my work with importing the functions related to matrices into my own module and modify them to work well with my own class of vector spaces. This will lay the foundation for working with vectors belonging to vector spaces of m x n matrices which lie under the real field of numbers. The tests for the modifications made will be pushed along with the code. I will submit a PR at the end of this two week period.

Week 6 to Week 8 (July 11 - July 25)

By this time, I plan to begin my work on implementing inner products and if that is completed before time, which it probably will, I will proceed to implement a function that can figure out whether a given vector space is an inner product space or not. I have set aside a two-week slot for this work because I need some buffer time in case I need to implement more functions to manipulate matrices or in case the time for the last two weeks falls short. Also, if any of the ideas mentioned in the "Open for discussion" subsection get more matured by this time, I will try to devote time to them during his period.

Milestone 2: Complete any unfinished work till this period for second evaluations by the mentor.

Week 9 (July 29 - August 5)

In this period, I will work on implementing the concept of orthogonality in linear algebra. This will involve not only checking if two given vectors are orthogonal but also if two vector spaces are orthogonal.

Week 10 to Week 12 (August 6 - End of coding period)

Buffer weeks for final revisions, merging the documentation and adding additional tests if required.

Platforms used

I work on MacOS Sierra 10.12.4. I prefer to use Sublime Text 3 because of its user interface and the varied functionality that it provides, from syntax marking to building your code locally.

Contributions to SymPy

Pull Requests

  • (Unmerged, Work-in-progress) Fixed str printer to create re-creatable implementations for sets #12435