Srajan Garg

IIT Bombay


Internships & Key Projects

Optimizing Linear Algerbra Routines with Data Prefetching
Harsha Vardhan, Microsoft Research Summer '17 + Ongoing

Machine learning algorithms are a combination of intricate subroutines which typically deal with TBs of data, which do not fit into physical memory. Among these routines, the most widely used ones are linear algebra (BLAS) routines, which are also the primary focus of the project. Unspecialized algorithms which run such routines directly from disk lead to thrashing which cause a drastic performance hit. Specialized out-of-core algorithms do take care of thrashing and locality but are limited by the data communication bandwidth. Our aim was to minimize this bottleneck and achieve speeds as fast as in-memory calculations.

To achieve this we first break the entire subroutine into smaller blocks whose data requirement is known and fits in RAM. For linear algebra routines, we also know the precise access patterns to these blocks. So, while the processor works on a particular block of data, we can prefetch the block required next, concurrently. Once the processor is done with the current task, it can seamlessly switch to the next task, whose data has already been prefetched to RAM.

We implement this technique for dense-dense matrix multiplication `blas_sgemm`, such that we achieve comparable speeds to in-memory computation while using only a small fraction of the RAM required for an in-memory execution of the routine. For eg, we multiply 200GB of matrices using only 4GB of RAM at 70% of the speed of pure in-memory computation. Further, 90% speeds can be achieved if some physical cores of the CPU are designated purely for the task of prefetching. We also observe similar results for sparse-dense multiplication `blas_csrmm`.

GAN-style Learning for Robustness of 3D Models
Prof. Siddhartha Chaudhuri, IIT Bombay
Vladimir G. Kim, Adobe Resarch Ongoing

I'm working on modifying GAN-style (generative adversarial) networks for learning robustness of 3D models as part of my Bachelor Thesis. The goal of the project is to modify an input voxel grid (a representation of a 3D model), so as to become more robust in general. Robust can have many definitions, for eg. toppling stability, stability when shot with a bullet etc.

The generator network produces modifications of an input object (a voxel grid) while maintaining shape similarity using a loss function. Ideally, we would like the generator network to function as an independent unit, and should not change with each 'robustness' specification. The adversarial network can be flexibly modeled to improve the generator according to the robustness specification.

Implementing Polynomial Module & Wrappers for SymEngine
Google Summer of Code Summer '16

SymEngine is a Computer Algebra System (CAS) written in C++, which is to be used as the future core for popular symbolic python library SymPy. I completely refactored and restructured the Polynomial module for SymEngine. This included choosing an appropriate class structure, implementing necessary member functions and integrate into already existing symbolic framework. Additionally, I introduced wrappers to polynomial classes of other popular CAS libraries like FLINT and Piranha. I also implemented conversions from symbolic expression tree to an appropriate polynomial type (including generator extraction) to help build the library’s Coercion Framework.

Besides my main project, I implemented a fast parser to convert mathematical expressions strings to the library’s symbolic expressions. Also, I improved the overall infrastructure of the library, contributed to make the Continuous Integration better and made changes to speed up build times by about 20%.

Do checkout my weekly blog linked below for a more indepth view into my progress and project!



Other Work Experience

Recommendation System for Personalized Learning
Silverleaf Capital Services, Mumbai Summer '16

Silverleaf is an algorithmic research firm, which partnered with an e-learning platform to reform their online education system. I designed a prediction and recommender system for this platform to suggest questions to students taking tests. The system learns student’s strengths and weaknesses in real-time, so as to provide questions as per the student’s competence while also ensuring that the questions are not redundant, thus maximizing student's efficiency and learning. I also developed sub-systems for the platform, which helps detect anomalies and erroneous questions.

The algorithm was deployed in D, using a popular collaborative filtering techniques, Singular Value Decomposition. A lot of my work was inspired from Netflix's Prize competition, where the aim was to develop a recommender system for movies. Naturally, there was an overlap in the problem, and I borrowed many ideas from algorithms of the winners of the competition. The final system showed significant improvements in measures like RMSE and F1 score.

Django based Management Information System
CityFlo, Mumbai Winter '15

Cityflo is a bus aggregator startup. I developed the backend for an operational customer support dashboard from scratch. This was used by the company’s customer support team to monitor bus activities, their locations and stop details as well as display information about the customers, their ride history, wallet transactions and their past grievances. I used the Django Object-Relational Map and optimized queries for fast data retrieval from a PostgreSQL database.

Another contribution I made was to shift the user bonus structure from a free credit system to a free ride system. Initially, user bonuses were gifted in the form of ride credits, essentially equivalent to money in the user's wallet. I changed it to a model where the user was offered a fixed number of free rides instead. This involved creating a new database class as well as migrating existing user data.



More Projects

Exact Geodesics on Polygonal Meshes
Prof. Siddhartha Chaudhuri, IIT Bombay Spring '17

The project deals with finding exact geodesics on a polygonal meshes. Geodesics usually refer to shortest distances on a surface. We implemented a window propagation algorithm based on the paper by V. Surazhsky et al. We also juxtapose the exact geodesic against the shortest path along the mesh edges, for visual clarity.

The algorithm tries to 'unfold' the polygonal mesh starting from the source, and then easily joins the source to the destinations using straight line on this unfolded plane. It does so by maintaining windows on each edge, from which the source can be seen using some unfolding. These windows are further propagated (in a Djikstra's fashion) along the mesh by updating and merging with existing windows. Although the worst case time complexity of the algorithm is O(N2logN), for all practical purposes it runs in sub-quadratic time.

Mesh Simplification with Error Quadrics
Prof. Siddhartha Chaudhuri, IIT Bombay Spring '17

The project deals with high quality approximations of a given polygonal mesh while still representing the original model as closely as possible. We make use of the algorithm mentioned in the paper by M. Garland et al, which uses iterative contractions of vertex pairs to minimize a specially constructed error metric. This produces simplified meshes with high resemblance to the original.

This was one of the mini-projects in our Digital Geometry course. Most of the code dealing with mesh input and visualization was already provided to us. Do checkout the github page for my results!

Compiler for subset of C
Prof. Uday Khedkar, IIT Bombay Spring '17

We designed and developed a compiler from scratch for C to generate MIPS assembly code. Compiler frontend was generated using flexc++ and bisonc++, while the abstract syntax tree and assebly generation backend was hand-written. We also wrote a dead code elimination algorithm to optimize the resulting intermediate code generated.

IIT Bombay Reddit
Prof. S. Sudarshan Chandran, IIT Bombay Autumn '16

We built an IIT Bombay exclusive version of the website reddit.com using the python backend framework Django, while keeping all the fundamentals of databases into play. Reddit is a social media and social news aggregation, web content rating and discussion website. It provides a platform for students to submit content via posts which may either be text based or external links. The content entries are organized into what are called subreddits, which are pages dedicated to a particular genre or topic. Other users can then vote on submissions to organize the posts and determine their position on the site’s pages. The submissions with the most positive votes appear on the main page or the top of a category. Users can also comment on posts as well as other users' comments, and these comments also have votes attached to them.

Feature Based Image Metamorphosis
Prof. Siddhartha Chaudhuri, IIT Bombay Autumn '16

The project deals with metamorphosis of one digital image into another in a fluid and seamless way. We make use of the algorithm mentioned in the paper by T. Beier et al. from SIGGRAPH ’92, which uses user specified features. These features are pairs of lines which map the same semantic feature (say eyebrows) on both the images, which are then utilized to create a smooth transformation of each pixel’s location using rotation, translation, and scaling, thereby morphing the whole image.

This was one of the mini-projects in our Computer Graphics course. Most of the code dealing with feature addition and retrieval was already provided to us. Do checkout the github page for my results!

Raytracer for 3D Rendering
Prof. Siddhartha Chaudhuri, IIT Bombay Autumn '16

Implemented an efficient ray-tracing algorithm for rendering 3D scenes and primitves. Apart from using the Phong reflection model for calculating surface color and shading, the tracer also supports refraction through primitves and three different kinds of light sources : Point, Directional and Area lights. Apart from this, I also implemented smooth normals for polygonal meshes, which render a very smooth shading for primitives.

Do check out the github page for sample rendered images!

Movie Recommendation Engine
Prof. Ganesh Ramakrishnan, IIT Bombay Spring '16

We developed a movie recommendation engine in Python using popular collaborative filtering techniques, motivated by the research previously done on the Singular Value Decomposition method during the Netflix Prize competition. We also implemented and tested other techniques like the k-Nearest Neighbors for comparison, observing that matrix factorization methods worked better.

Image Interpolator in VHDL
Prof. Supratik Chakraborty Autumn '15

We created an image interpolator in a hardware description language, VHDL. The project included creating an optimal datapath to produce an interpolated image from an incoming stream of pixels of an input image. And also designing an optimized controller module to achieve minimum possible delay and internal space requirement. This was done by building different blocks to decode the pixel stream, store them in a grid-like fashion and output interpolated pixels as a stream.

TwoCube: a 3D Isometric Puzzle Game
Runner Up, Microsoft’s code.fun.do Autumn '15

Ideated and implemented a 3D Isometric game using a mixture of elements from the popular games of Tetris and 2048, using the Unity Game Engine. Apart from being the runner-up at Microsoft's code.fun.do Hackathon, the game also bagged the first place at Lenovo's Game development competition and won us a handsome 50K rupees prize!

Department Allocation as a Matching Problem
Prof. Sharat Chandran, IIT Bombay Autumn '15

We built a full stack web application to allocate departments to students based on their preferences, GPA and branch strength constraints. We reduced branch allocation to a variation of the stable matching problem.

It was solved using a modification of the Gale Shapley algorithm along with improvements like cyclic preference resolution while also following specifications mentioned in the IIT Bombay rulebook. Apart from this, we implemented official LDAP authentication for students and administrators.

Eight Ball Pool
Prof. Sharat Chandran, IIT Bombay Autumn '15

We implemented a simplified implementation of 8 Ball Pool in C++. The implementation includes basic aspects of the game like friction, collisions with restitution and pocket detection, while also enforcing the rules of the game. We used the famous Box2D physics simulation engine which is itself based on OpenGL.

YouTuber : Music & Metadata Downloader Webapp
Self Project Autumn '15

Hate unorganized music libraries? Hate it when the music you download off YouTube has no album art or artist information tagged? Then this webapp is for you!

A webapp to download your favourite music off of YouTube, with all the relevant metadata. Four types of ID3 tagging are done, the title, artist and album and also the corresponding album art. The first three are extracted using the song title from YouTube itself. The album art is found by scraping google images. Also prompts user for any changes they want to make to the data. It then downloads the .mp3 file, applies the metadata and finally serves it to the client.



Courses

Theoretical CS
  • Data Structures and Algorithms
  • Analysis and Design of Algorithms
  • Digital Logic and Design
  • Artificial Intelligence
  • Data Analysis and Interpretation
  • Discrete Structures
  • Logic for Computer Science
Applied CS
  • Fundamentals of Machine Learning
  • Computer Graphics
  • Digital Geometry Processing
  • Information Retrieval and Web Mining
  • Network Security and Cryptography
Systems
  • Compilers & Programming Languages
  • Computer Networks
  • Software Systems
  • Databases
  • Operating Systems
  • Computer Architecture
Mathematics & Others
  • Numerical Analysis
  • Derivative Pricing
  • Calculus
  • Linear Algebra
  • Differential Equations
  • Quantum Physics