Abstract

The bundle adjustment (BA) problem is formulated as a non linear least squares problem which, requires the solution of a linear system. For solving this system, we present the design and implementation of a fast preconditioned solver. The proposed preconditioner is based on the deflation of the largest eigenvalues of the Hessian. We also derive an estimate of the condition number of the preconditioned system. Numerical experiments on problems from the BAL dataset [3] suggest that our solver is the fastest, sometimes, by a factor of five, when compared to the current state-of-the-art solvers for bundle adjustment.

Abstract

As a big data application, extreme multilabel classification has emerged as an important research topic with applications in ranking and recommendation of products and items. A scalable hybrid distributed and shared memory implementation of extreme classification for large scale ranking and recommendation is proposed. In particular, the implementation is a mix of message passing using MPI across nodes and using multithreading on the nodes using OpenMP. The expression for communication latency and communication volume is derived. Parallelism using work-span model is derived for shared memory architecture. This throws light on the expected scalability of similar extreme classification methods. Experiments show that the implementation is relatively faster to train and test on some large datasets. In some cases, model size is relatively small. Code: https://github.com/misterpawan/DXML

Abstract

In this paper, we study FPGA based pipelined and superscalar design of two variants of conjugate gradient methods for solving Laplacian equation on a discrete grid; the first version corresponds to the original conjugate gradient algorithm, and the second version corresponds to a slightly modified version of the same. In conjugate gradient method to solve partial differential equations, matrix vector operations are required in each iteration; these operations can be implemented as 5 point stencil operations on the grid without explicitely constructing the matrix. We show that a pipelined and superscalar design using high level synthesis written in C language leads to a significant reduction in latencies for both methods. When comparing these two, we show that the later has roughly two times lower latency than the former given the same degree of superscalarity. These reductions in latencies for the newer variant of CG is due to parallel implementations of stencil operation on subdomains of the grid, and dut to overlap of these stencil operations with dot product operations. In a superscalar design, domain needs to be partitioned, and boundary data needs to be copied, which requires padding. In 1D partition, the padding latency increases as the number of partitions increase. For a streaming data flow model, we propose a novel traversal of the grid for 2D domain decomposition that leads to 2 times reduction in latency cost involved with padding compared to 1D partitions. Our implementation is roughly 10 times faster than software implementation for linear system of dimension 10000 × 10000. Index Terms—FPGA, High Level Synthesis, Conjugate Gradient, Laplace System, Pipelining, Superscalarity.

Abstract

Datasets play an important role in driving innovation in algorithms and architectures for supervised deep learning tasks. Numerous datasets exist for images, language translation, etc. One of the interesting challenge problems for deep learning is to solve high school problems in mathematics and sciences. To this end, a comprehensive set of dataset containing hundreds of millions of samples, and the generation modules is required that can propel research for these problems. In this paper, a large set of datasets covering mathematics and science problems is proposed, and the dataset generation codes are proposed. Test results on the proposed datasets for character-to-character transformer architecture show promising results with test accuracy above 95%, however, for some datasets it shows test accuracy of below 30%. Dataset will be available at: www.github.com/misterpawan/scimat2.

Abstract

A fast, robust, parallel, and parameter free version of a frequency filtering preconditioner is proposed for linear systems corresponding to diffusion equation on a structured grid. Proposed solver is faster than the state-of-the-art solvers

Abstract

Datasets play an important role in driving innovation in algorithms and architectures for supervised deep learning tasks. Numerous datasets exist for images, language translation, etc. One of the interesting challenge problems for deep learning is to solve high school problems in mathematics and sciences. To this end, a comprehensive set of dataset containing hundreds of millions of samples, and the generation modules is required that can propel research for these problems. In this paper, a large set of datasets covering mathematics and science problems is proposed, and the dataset generation codes are proposed. Test results on the proposed datasets for character-to-character transformer architecture show promising results with test accuracy above 95%, however, for some datasets it shows test accuracy of below 30%

Abstract

We present the design and implementation of Two-Grid Preconditioned Bundle Adjustment (TPBA), a robust and efficient technique for solving the non-linear least squares problem that arises in bundle adjustment. Bundle adjustment (BA) methods for multi-view reconstruction formulate the BA problem as a non-linear least squares problem which is solved by some variant of the traditional LevenbergMarquardt (LM) algorithm. Most of the computation in LM goes into repeatedly solving the normal equations that arise as a result of linearizing the objective function. To solve these system of equations we use the Generalized Minimal Residual (GMRES) method, which is preconditioned using a deflated algebraic two-grid method. To the best of our knowledge this is the first time that a deflated algebraic twogrid preconditioner has been used along with GMRES, for solving a problem in the computer vision domain. We show that the proposed method is several times faster than the direct method and block Jacobi preconditioned GMRES.

Abstract

We propose Domain Decomposed Bundle Adjustment (DDBA), a robust and efficient solver for the bundle adjustment problem. Bundle adjustment (BA) is generally formulated as a non-linear least squares problem and is solved by some variant of the Levenberg-Marquardt (LM) algorithm. Each iteration of the LM algorithm requires solving a system of normal equations, which becomes computationally expensive with the increase in problem size. The coefficient matrix of this system has a sparse structure which can be exploited for simplifying the computations in this step. We propose a technique for approximating the Schur complement of the matrix, and use this approximation to construct a preconditioner, that can be used with the Generalized Minimal Residual (GMRES) algorithm for solving the system of equations. Our experiments on the BAL dataset show that the proposed method for solving the system is faster than GMRES solve preconditioned with block Jacobi and more memory efficient than direct solve.