Abstract

Presburger arithmetic provides the mathematical core for the polyhedral compilation techniques that drive analytical cache models, loop optimization for ML and HPC, formal verification, and even hardware design. Polyhedral compilation is widely regarded as being slow due to the potentially high computational cost of the underlying Presburger libraries. Researchers typically use these libraries as powerful black-box tools, but a lack of internal documentation and decade-old C implementations hold back broader performanceoptimization efforts. With FPL, we introduce a new library for Presburger arithmetic built from the ground up in modern C++. We carefully document its internal algorithmic foundations, use lightweight C++ data structures to minimize memory management costs, and deploy transprecision computing across the entire library to effectively exploit machine integers and vector instructions. Major parts of our library have already been upstreamed into the LLVM/MLIR open source project, and this functionality is being used by MLIR to perform loop fusion. On a newly-developed comprehensive benchmark suite for Presburger arithmetic, we show a 5.25x speedup in total runtime over the state-of-the-art library isl in its default configuration and 3.14x when over a variant of isl optimized with elementwise transprecision computing. We expect that the availability of a well-documented and fast Presburger library will accelerate the adoption of polyhedral compilation techniques in production compilers.

Abstract

Multi-robot systems have many applications where a group of robots carry out a certain task more efficiently than a single robot. One of the most practical implementations of such a system is to transport large payloads using multiple small robots. Such a payload transportation system can be used in large warehouses, rescue operations during natural disasters and patient transportation in hospitals. Food and package delivery systems are also possible to design by extending these concepts to multiple drones. In the case of rigid payloads, the robots must group in a static formation as per the shape of the payload so that it can be transported. However, when it comes to deformable payloads, the process becomes complicated due to the flexible nature of the payload. In addition to that for efficient transportation of the deformable payload the robots must be able to reshape the formation to squeeze through the narrow gaps among the obstacles. In this thesis, we present a methodology for transportation of deformable payloads using a formation of non-holonomic mobile robots, while avoiding static and dynamic obstacles. This work is an endto-end solution which includes creating initial formation of the robots, path planning to avoid static obstacles, dynamic obstacle avoidance, control signal generation for individual robots and building a local positioning system for localization of individual robots as well as the formation. We assume the center of the formation to be a virtual robot which also plays the role of the leader of the formation. Rapidly exploring Random Tree star (RRT*) algorithm is used to determine static obstacle free trajectory for the virtual leader while a custom path planning algorithm is incorporated for the follower robots. Individual trajectories are planned for each of the robots. A decentralized leaderfollower formation control is applied for the robots to traverse on their respective trajectories without breaking the formation while following the constraints of the deformable payload. The virtual leader moves forward or backward on the initially generated path with variable velocity depending on the proximity of dynamic obstacles. All the other robots follow it so that the formation can avoid dynamic obstacles while remaining on the path leading towards the destination. In order to carry out the process smoothly we created a local position system using Ultra Wide Band (UWB) modules which can localize each of the robots in the formation in real time.

Abstract

Focus, defocus and depth-of-field are integral aspects of a photograph captured using a wide-aperture camera. Focus and defocus blur provide critical cues for estimation of scene depth and structure which helps in scene understanding or post-capture image manipulation. Focus and defocus blur are also used creatively by photographers to produce remarkable compositional effects such as emphasis on the foreground subject with aesthetic bokeh in the background. Epsilon Focus Photography is a branch of computational photography that deals with the capture and processing of multi-focus imagery - where multiple wide-aperture images are captured with a small change in focus position. In this thesis, we provide a comprehensive study of various problems in epsilon focus photography along with a detailed analysis of the related work in the area. We provide useful constructs for the understanding and manip- ulation of focus, defocus blur and the depth-of-field of an image. The work in this thesis can be divided into four broad categories of measurement, representation, manipulation and applications of focus. Measuring focus is a long studied and challenging problem in computer vision. We study various methods to measure focus and propose a composite measure of focus that combines the strengths of well-known focus measures. We the study the task of post-capture focus manipulation at each pixel in an image and formulate a novel representation of focus that can find much use in image editing toolkits. Our representation can faithfully encode the fine characteristics of a wide-aperture image even at complex interaction locations such as depth-edges and over-saturated background regions, while optimizing the memory footprint of multi-focus imagery. Apart from precise geometric constructs for scene refocusing, we also propose an data-driven approach for post-capture scene refocusing using deep adversarial learning. We show how the tasks of deblurring an image, magnification of the defocused content and overall comprehensive focus manipulation can be efficiently modeled using conditional adversarial networks. We study several applications of focus in computer vision such as view interpolation and depth-from-focus. We provide a tool that can interpolate different views of a scene based on focus texture segmentation and propose a novel solution for depth-from-focus using the proposed composite focus measure. In summary, this thesis consists of a comprehensive study of epsilon focus photography and its applications in the context of computer vision and computational photography.

Abstract

With the advent of intelligent transport, quadrotors are becoming an attractive solution while lifting or dropping payloads during emergency evacuations, construction works, etc. During such operations, dynamic variations in (possibly unknown) payload cause considerable changes in the system dynamics. However, a systematic control solution to tackle such varying dynamical behaviour is still missing. In this work, two control solutions are proposed to solve two specific problems in aerial transportation of payload, as mentioned below. In the first work, we explore the tracking control problem for a six degrees-of-freedom quadrotor carrying different unknown payloads. Due to the state-dependent nature of the uncertainties caused by variation in the dynamics, the state-of-the-art adaptive control solutions would be ineffective against these uncertainties that can be completely unknown and possibly unbounded a priori. In addition, external disturbances such as wind while following a trajectory in all three positions and attitude angles. Hence, an adaptive control solution for quadrotors is proposed, which does not require any a priori knowledge of the parameters of quadrotor dynamics and external disturbances. The second work is focused on the interchanging dynamic behaviour of a quadrotor while loading and unloading different payloads during vertical operations. The control problem to maintain the desired altitude is formulated via a switched dynamical framework to capture the interchanging dynamics of the quadrotor during such vertical operations, and a robust adaptive control solution is proposed to tackle such dynamics when it is unknown. The stability of the closed-loop system employing both the proposed controllers are studied analytically via Lyapunov theory. Further, the effectiveness of the proposed solutions is verified by deploying the controller on a realistic simulator under various scenarios and by testing the performance by comparing them with state-of-the-art controllers.

Abstract

This thesis concerns the subject of integer partitions. It has found numerous applications including in the study of black holes and in the area of statistical mechanics. A major area of investigation in its own right, it has been called “topic filled with the true romance of mathematics”. Our investigation leads to following results in the subject: • A combinatorial identity for the number of integer partitions of n in terms of certain weighted integer compositions of n. • A combinatorial identity for the sum of positive divisors of n in terms of certain weighted integer compositions of n. • A combinatorial identity for the number of representations of a positive integer n as a sum of k squares. • A combinatorial identity for the number of representations of a positive integer n as a sum of k triangular numbers. • A combinatorial identity for the number of plane partitions of a positive integer n. • Some combinatorial identities for the Bernoulli numbers in terms of Stirling numbers of the second kind. In deriving each of the above results, we highlight a useful combination of generating function techniques with the Faa di Bruno formula.

Abstract

As ever-increasing populations from around the world gain access to digital technologies, enabling them access to information, and thus knowledge, rights, and justice, it is imperative to ensure inclusiveness and accommodate the multitudes of languages used by them. As the computing machines and methods have got more sophisticated and gained capabilities by leaps and bounds, the use of these methods to automatically process human language has gained traction. However, this usually comes at a cost of expensive resource creation and computation to build and run these systems, and has limited the inclusiveness of the recently proposed state of the art systems for language processing to resource scarce languages and domains. Transfer Learning methods aim to dispel this limitation by leveraging pre-trained systems on existing large resources to adapt to serve the low resource domains, tasks, and languages. Research into these methods has gained increased attention as they have proven their efficacy at mitigating the resource constraint across tasks, domains and languages. This study focuses on exploring these transfer learning approaches in the context of presently used Indian languages, particularly Hindi and its code-mixed English-Hindi form, which is widely popular on social media. We explore both across task and cross-lingual transfer approaches towards a variety of downstream tasks, and successfully show their efficacy in the context of resource constrained training data and compute resources. We explore a syntacticosemantic curriculum learning based formulation to explore English-Hindi codemixed sentiment analysis, and show significant gains in performance. We also explore a variety of lexical and sentence level cross lingual transfer approaches for discourse analysis, and demonstrate their efficacy under different training regimen for discourse relation task. We also compare these approaches and gain insights into the nature of the cross-lingual transfer.

Abstract

Approximate Computing is revolutionizing the way we look at the VLSI design flow from RTL design based micro-architectures to standard cell characterization, by adding a quality relaxation constraint that is born out of the error resilience of modern applications. With the unprecedented increase of data-driven approaches and the need to generalize these approaches over multi-class problems, it is imperative that the traditional methods of delivering consistent precision have to adapt. On the other hand, this does not give us a complete free reign over the chip design flow, as unless an acceptable quality is maintained, the overall system failure is inevitable. Approaching physical limits in the fabrication at the current technology nodes and the growing reliability concerns in the manufacturing process have not only made the paradigm shift towards approximate computing attractive, but a necessity. Approximate Computing has enabled trade-offs between acceptable level of accuracy with the leakage and dynamic power dissipation, area, critical path delay and energy consumption of the chip. Previous approaches in approximate computing have been targeted towards ad hoc and automated approaches alike. The main contribution of this thesis is improvement in these areas with novel approaches to achieve better quality and other performance metric trade-offs. This thesis explores the following major avenues in approximate computing: 1. Arithmetic circuits are the fundamental blocks in any design or architecture. Particularly, optimizing multipliers can bring about a significant edge in terms of performance, power and area. This is achieved by developing a novel and performance efficient design of an approximate multiplier using the Toom-Cook multiplication algorithm. The N-bit multiplier complexity is reduced to O(Nlogd(2d−1)) from O(N2 ), for order d. As a result, on an average, the proposed multiplier achieves 53%, 18% and 57% improvements in area, delay and power only with less than 1% mean error. 2. Approximating Fast Fourier Transform architecture can accelerate numerous digital signal and image processing application domains. In this respect, a shared memory FFT architecture is developed using the proposed Approximate Toom-Cook multiplier. Since the entire frequency domain output is not usually required, another feature of the design is a supporting function in error correction based on the sparsity patterns. The design synthesized as such shows on average, a 49% and 53% improvement in consumption of area and energy, respectively, with as less error as 0.1% with pruning based on the sparsity patterns. Approximating the Full adder standard cells by pruning transistors have enabled us to achieve cells tuned to a more power-quality optimal point. This is essential as the leakage power has increased substantially with technology scaling and has become a dominant component of power dissipation, limiting the performance of the circuits. Significant leakage reductions up to 67% are obtained through the combined efforts of optimal transistor sizing and approximate computing

Abstract

There are many sub-fields of Artificial Intelligence of which Natural Language Processing (NLP) is the one which deals in providing the knowledge to computers to produce and understand human text and speech. Machine Translation (MT) is an application of NLP that focuses on the automatic translation between languages. It is crucial as it has enabled people all over the world to travel to various countries and interact with each other. With the recent advancement in deep learning, Neural Machine Translation (NMT) has shown indistinguishable translations from translations produced by humans for many language pairs, but driving factors behind the leaps in translation quality is availability of abundant parallel data resources which low resource languages lack like Indian languages. A lot of research has been done to improve the translation quality of low resource via exploiting monolingual data or parallel data involving other language pairs. Recently, Multilingualism has drawn much attention and is gradually becoming ubiquitous in the sense that more and more researchers have successfully shown that using additional languages helps in improving the translation quality. Indian languages are diverse, morphologically rich and use different scripts which make Translation tasks complex and challenging. But despite all this, Indian languages still share a lot of lexical features which we think can be utilized to improve the quality of translation systems. So, we performed a large scale case study on similarity among those languages by considering all the different factors that may impact its value. We have also proposed the techniques for efficient Multilingual Neural Machine Translation (MNMT) particularly for Indian languages mainly focusing on leveraging the lexical similarity of languages and efficient training in terms of time as well as computational resources. For this, we are performing a systematic incremental case study on MNMT where we are investigating the contribution of different languages during the learning process. Based on the facts and conclusion from our study, we devised an algorithm that will select the subset of languages for required for particular multilingual NMT settings. Also languages itself can also have multiple domains, making the available parallel data for particular domains very limited thus to address the problem of data scarcity, we propose the pipeline for efficient multilingual multi-domain systems. This is the first large-scale study specifically devoted to improve the MNMT for Indian languages by utilizing language relatedness to the best of our knowledge.

Abstract

The thesis talks about our novel architecture about the quasi-static world to formulate real-time object-based monocular Simultaneous Localization and Mapping (SLAM) for objects present in a scene. Here we propose our novel line-based parameterization for category-specific 3D CAD models. Using the vastly available 3D CAD model collection we have created category-level models for objects, which is in contrast with existing approaches that incorporate object-level models. The proposed parameterization associates the 3D category-specific CAD model and the object present in our scene using a dictionary-based RANSAC method that employs object viewpoint as prior and edges detected in the respective intensity image of the scene. The association problem posed here is tackled as a classical geometry problem rather than being dataset driven, thus saving the time and labor that one invests in annotating dataset to train Keypoint Network[25, 26] for different category objects. The proposed approach not only eliminates the need for dataset preparation, collecting a huge amount of object-level models, and annotating them but also speeds up the entire process as this method processes the image only once for all objects, thus eliminating the need of invoking the network for every object in an image across all the frames. A 3D-2D edge association module followed by a resection algorithm for lines is used to recover object poses. The formulation optimizes for the shape and pose of the object, thus aiding in recovering object 3D structure more accurately. Finally, a Factor Graph formulation is used to combine object poses with camera odometry that helps in formulating the optimization as a SLAM problem. The proposed category-level model-based approach has several other applications, such as retrieval of objects, which is an integral part of Augmented Reality applications. The architecture has been evaluated both qualitatively and quantitatively in a variety of indoor real-world environments, infused with several camera and objects motion challenges, depicting the usefulness of an instance independent monocular object SLAM and the advantage it enjoys over existing feature-based SLAM approaches.

Abstract

In 1957, Noam Chomsky’s revolutionary treatise, Syntactic Structures [45], established the foundations for a formal study of natural language syntax. Such a study requires the development of a mathematical paradigm where the grammatical structure of the language can be analyzed sans the semantic conditions responsible for the “possibility” or truth-value of the sentence, hence colourless green ideas sleep furiously. The work of Chomskyian linguistics in differentiating shallow and deep structures perpetuated the ideas of a rigid motif of structural integrity to language, which was often challenged by semanticists. However, it established the path of the study of natural language by the medium of syntax, therefore impressing upon the need to understand the sentence structure as a method of analyzing the language in a typologically uniform and relevant manner. In this thesis, we study the computational and representational offshoot of syntactic structures. The development of formal grammars allows mathematicians to leverage simply typed lambda calculus into the study of constituency grammar. This subsection of mathematical linguistics, known as categorial grammar, aims to study the functions responsible for combining constituents in a grammatical manner, viz with a view towards composition and compositional semantics. Theoretical work in this direction was motivated by theories such as AB-grammars [4, 10], Lambek calculus [76], Combinatory Categorial Grammar [124], Tree Adjoining Grammar [65], and Abstract Categorial Grammars [53]. Hindi has been largely underrepresented in these formal analyses of grammar, partly due to lack of exposure and partly due to the underlying strongly motivated syntactic analysis of the Paninian Grammatical Framework [17]. Therefore in this thesis, I aim to use a simplification of the Lambek calculus framework, known as pregroup grammar [78] in order to understand the syntactic phenomena underlying the language, when considered devoid of semantic considerations. Pregroup grammars are a simple categorial grammars which have been used to study languages like Japanese, Sanskrit and Persian, along with English, French, Hungarian and others, ensuring a diverse body of literature and surrounding operators and operations for representing constituency information. In this thesis, I study the basic syntactic features of the Hindi language in terms of the word order, noun phrase characteristics, verb phrase characteristics, and formalize the agreement rules between them. I explore the representation of these properties in a consistent manner without relying on lexical semantic characteristics as much as possible. I then delve into the interoperability of relatively free word order syntactic constituent representations, their exploration in dependency syntax, and some possible applications of an advancement in constituency representation with the development of a hybrid grammaticality checker