Complexity Analysis of Vedic Mathematics Algorithms for Multicore Environment

Complexity Analysis of Vedic Mathematics Algorithms for Multicore Environment

Urmila Shrawankar (G. H. Raisoni College of Engineering, Nagpur, India) and Krutika Jayant Sapkal (G. H. Raisoni College of Engineering, Nagpur, India)
Copyright: © 2017 |Pages: 17
DOI: 10.4018/IJRSDA.2017100103
OnDemand PDF Download:
$37.50

Abstract

The huge computations performed sequentially requires a lot of time for execution as on contrary to the concurrent implementation. Many problems are involved in the dense linear algebra operations the main focus for this work is for solving linear equations. The problem of solving linear equations when approached using parallel implementation will yield better results. The Vedic mathematical method of Paravartya Yojayet is having less complexity as compared to the conventional methods. This work mainly focuses on the parallel implementation of the Paravartya Yojayet and its comparison to the benchmarking of the existing LU decomposition. The results of this implementation of Paravartya Yojayet are better when analysed theoretically but its actual parallel implementation will vary so it needs to be analysed and this work presents the same. The comparative analysis of the two ways for parallelization of the Paravartya Yojayet methods viz. ‘For loop' parallelization and the ‘direct parallelization' is also analysed in this work.
Article Preview

1. Introduction

The current drift of technology as predicted by Moore was of inducing more number of semiconductors on a smaller chip. This has change the face of technology increased the computational power of even a small hand held device. But it was perceived that only the hardware evolution was not adequate enough. The software also needed to make leap in a way to complement the upgraded hardware configuration. This lead to the concept of concurrent execution of programs on shared memory system with more than one processors (cores).

The effect of the changing architecture can be very well be seen on the problems that are of the category of dense linear algebra such as the Linear Equation solving. These problems expect one of the two solutions as given below.

  • 1.

    Amendment in the existing algorithm.

  • 2.

    Use of new programming paradigms or libraries.

There are many existing methods available to solve Linear Equations; listed below.

  • 1.

    LU Decomposition

  • 2.

    Gaussian Elimination

  • 3.

    Gaussian Elimination using Pivoting

  • 4.

    Cholesky Factorization

The above said methods give a better speedup; but when implemented concurrently; it will not reach to the expected speedup.

Some factors which affect the speed up of parallelization are mentioned below.

  • 1.

    Inter – process dependencies

  • 2.

    Idling

  • 3.

    Excess Communication

Dense linear algebraic equations are implemented in parallel using GPU based systems, the load balancing methods and it also uses the static and dynamic paradigms of available parallelization libraries.

These methods are not as efficient and the increasing expectations won’t be fulfilled by them. The solution to this dilemma exists in the ancient Indian scriptures. The ancient Indian scriptures mainly the Atharvaveda’s sub-section (Upveda) named “Sthapathyaveda” it contains account of all the engineering and architecture related works. These scriptures also consist various different method to deal with linear equations that are very aptly decrypted by Sri Krsna Tirthaji Maharaj (Tirthji, Sri Bharti Krsna (Bankagarya of Oovardhana Matha, 1981). These methods are way better than the conventional methods. The methods available for solving linear equations in Vedic mathematics are listed below.

  • 1.

    Paravartya Yojayet

  • 2.

    Sunyam Anyat

  • 3.

    Sankalana Vyavakalanabhyam

  • 4.

    Sopantyadvayamantyam

But the biggest question that surfaced was will these methods be able to adapt the parallelization? Will the method be able to deliver the immense performance of sequential implementation even in the parallelized form?

The rest of the article will contain the following aspects of the work; section two consist the related work and comparative analysis of the conventional method and Vedic method. Section three will contain the analysis of the parallelizability of Paravartya Yojayet and LU Factorization. Section four will highlight Factors that could affected the time complexity of the parallel implementation. Section five will contain a detailed analysis of the Results along with the discussions. Section six will be concluding remarks for the work and the section seven the future scope of the work.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 4: 4 Issues (2017)
Volume 3: 4 Issues (2016)
Volume 2: 2 Issues (2015)
Volume 1: 2 Issues (2014)
View Complete Journal Contents Listing