norman

Parallel Implementation of Backward Substitution in Gaussian Elimination to Solve Systems of Linear Equations

norman — Mon, 21 Jul 2008 05:21:11 GMT

Many practical problems, including problems in Mathematics itself can be modeled as Systems of Linear Equations. This suggests that methods to solve such systems are of high interest. One method that is often used in practice is the Gaussian Elimination as it uses reasonable computing time and storage demand. In addition to that, the computing time can be improved by implementing the algorithm in parallel. This paper shows the parallel implementation of the backward substitution process within the Gaussian Elimination. The implementation uses distributed memory model or message passing mechanism. Specifically, it uses the C++ programming language and the MPI library.

Parallel Implementation of Simpson’s Rule for Numerical Integration to approximate the value of Pi

norman — Fri, 13 Jun 2008 07:30:53 GMT

Abstract

Parallel implementation of an algorithm is of high interest because it brings speed up to the execution time of that algorithm. Numerical Integration such as Simpson’s Rule is an example of Numerical Method that can be fully implemented in parallel thru data parallelism (domain decomposition). This paper shows the parallel implementation of Simpson’s Rule to approximate the value of Pi by following Foster’s methodology and using the message passing mechanism. This paper also highlights that parallelism in Numerical Methods is not without problem; parallelism may produce less accuracy due to Error Propagation. It is something that needs to be seriously considered in implementing Numerical Methods in parallel.

Keyword: Parallelism, Simpson’s Rule, Error Propagation, Foster Methodology, Message Passing.

Diagnosing Diabetes Mellitus Using Probabilistic Neural Networks

norman — Fri, 02 May 2008 16:37:39 GMT

In the previous report ¹⁾, it has been designed a Neural Networks System to forecast the onset of Diabetes Mellitus. Here, another Neural Networks approach/algorithm is used. It is the Probabilistic Neural Networks as described by Donald F. Specht ²⁾. The simulation shows the Probabilistic Neural Networks can forecast the onset of Diabetes Mellitus with 100% accuracy.

Note: This report is basically just an addition to the earlier paper titled "Using of Feed-Forward Backpropagation Neural Network to Forecast the onset of Diabetes Mellitus". So, for more details on problem description, data, etc, please refer to this paper.

Using of Feed-Forward Backpropagation Neural Network to Forecast the onset of Diabetes Mellitus

norman — Sat, 26 Apr 2008 08:35:41 GMT

Diabetes Mellitus is a disease that can cause many serious complications. A proper treatment is needed for the patient who has it. In order to that, first we need to recognize whether a person has Diabetes or not. This paper outlines the design, training and simulation of a Feed-Forward Backpropagation Neural Network that can forecast the onset of Diabetes Mellitus in a person with more than 90% accuracy

Comparing Graph Traversal Algorithms: Depth-First Search and Breadth-First Search

norman — Sat, 26 Apr 2008 08:29:38 GMT

Many graph algorithms require processing vertices or edges of a graph in systematic fashion. There are two principal for doing such traversals: Depth-First Search (DFS) and Breadth-First Search (BFS). This very brief paper compares the two algorithms. It outlines the differences and the similarities between the two.

Explaining Dynamic Programming Algorithm To Solve All-Pairs Shortest Paths Problem

norman — Sat, 26 Apr 2008 08:25:46 GMT

All-Pairs Shortest Paths Problem is a problem of interest as it has many practical uses. One example is to make table of distance between all pairs of cities for a road atlas. Dynamic Programming is a powerful technique that can be used to solve this problem. It is because the problem has the overlapping sub-problems property and optimal sub-structure property, both are properties required so that the problem can be solved using Dynamic Programming technique. Overlapping Sub-problems is one thing that can make other technique such as Divide and Conquer to yield algorithm with exponential time complexity, because it always re-compute the same sub-problems. The power of Dynamic Programming is that it uses bottom up approach and memoization that ensure the same sub-problem is computed only once and the result is stored for later use. No need for a re-compute. This paper explains the application of Dynamic Programming in solving the All-Pairs Shortest Paths Problem.

Solving 0-1 Knapsack Problem using Dynamic Programming

norman — Sat, 26 Apr 2008 08:07:39 GMT

Knapsack Problem has many variations. One popular variation is 0-1 Knapsack Problem. This problem occurs in many ways in real-life. So, solution for this problem is of interest. The Exhaustive Search approach (Brute Force) yields an exponential running time. This paper explains Dynamic Programming algorithm to solve this problem that results improvement in the solution running time. The paper also explain the enhancement of the traditional bottom-up Dynamic Programming approach with the combination of the Top-Down approach that results a technique called Memory Functions

Greedy Algorithms to solve Minimum Spanning Trees Problem

norman — Sat, 26 Apr 2008 08:00:57 GMT

Minimum Spanning Tree problem is an example of Optimization problem. This kind of problem can be solved with technique such as the Greedy technique. This paper explains two algorithms to solve this problem that is based on such Greedy technique; the Kruskal’s algorithm and the Prim’s algorithm. The paper emphasizes on the application of the Greedy technique to solve the problem. It will also compare the two algorithms with algorithms for other problems (Connected Components algorithm and Dijkstra’s algorithm) as similar techniques are used in these algorithms. Then, the paper will show that running time/complexity of Prim’s algorithm can be improved by using Fibonacci Heap data structure so that it runs faster than Kruskal’s algorithm

Explaining Dijkstra Algorithm - Greedy Technique to solve Shortest Path Problem

norman — Sat, 26 Apr 2008 07:55:18 GMT

Dijkstra’s algorithm is a well known algorithm to solve the single-source shortest paths problem. This paper explains the algorithm by focusing on the algorithm design technique used, which is the Greedy Technique. This technique works well to the problem because the problem has the Optimal Substructure property. To show the formal proof of correctness of this algorithm, the Loop Invariant technique is used. Finally, the paper shows that Dijkstra’s algorithm complexity is determined by the implementation of the data structure used in the algorithm. The goal of this paper is to emphasize that in explaining an algorithm, one must show the design technique used, its formal proof of correctness and its complexity analysis. All these three must present, otherwise the algorithm is considered incomplete.

In Search Of Optimal Mathematics Algorithm

norman — Sat, 26 Apr 2008 07:51:19 GMT

In designing an algorithm for a mathematical concept, one may need to look beyond the definition of that mathematical concept in order to get an optimal algorithm. The complexity of an algorithm for a mathematical concept is not necessarily bounded by the complexity of brute-force algorithm as per its mathematical definition. This paper makes this exposition by using matrix multiplication as an example. Straight forward computation as per the definition of matrix multiplication is an algorithm with complexity . It is not optimal. By looking beyond the definition, Strassen could come up with algorithm which complexity is . Further efforts resulting the Coppersmith-Winograd algorithm which complexity is only . Later, Umans and Cohn, together with Kleinberg and Szegedy made two conjectures that either one would imply that the exponent of matrix multiplication is 2. Just like its lower bound.