sharadsinha

Posts Tagged ‘Numerical Algorithms’

What is there in the word “distance”?

In Education, Mathematics on February 6, 2013 at 9:32 PM

I fist learned about distances in school- class of classical geometry. Of course it was not called classical geometry in school but only geometry. The initial concepts were related to distances between points in a plane, between lines in a plane and between a line and a point in a plane. A plane, as you know, is a  2-dimensional (2D) space. In high school, this concept was extended to 3-dimensional space (3D). The concept of distance basically gives an idea of how far (or how close) are two things (lines, points) from (to) each other. What I learned was “2-norm distance” (the typical Euclidean distance):

2-norm distance = \sqrt{(\displaystyle\sum_{i=1}^{n} |{x_{i}}^2 - {y_{i}}^2|)}

I learned about Hamming Distance during my undergraduate courses on electronics communication. However, it is only during research that I learned a lot more about distances. My first surprise came when I heard about distances in a class on image processing. You can use distances to measure similarity between images! Of course the definitions and methods to calculate those distances were also different. Since then I have learned about distances being one major way of identifying similarities between objects or classes of objects. The central idea behind all these different kinds of distances (not just in image processing) remains the same: to measure  how far the objects are from each other in some respect. For instance, in psychoanalysis “Emotional Distance” is the degree of emotional detachment from some person or events; Czekanovski-Dice distance is used to compare two audio waveforms x and y in time domain etc. If your distance from the world of distances is not big ;), you might want to try reading the Dictionary of Distances.

Numerical Stability in Calculations

In Design Methodologies, Embedded Systems, Engineering Principles, Mathematics on January 24, 2013 at 11:44 PM

I did not have any course on algorithms in my undergraduate education. I studied about them (their properties, design etc.) during my research work. I now realize why their study is important for anyone who wants to be really good at designing algorithms or implementing them. After all, algorithms solve problems. I recently came across the subject of numerical stability of algorithms, numerical algorithms to be precise. While algorithms help solve problems, they need to be implemented on a digital machine (a computer for example) which has limited precision. Whatever number system we use, they cannot cover all the numbers present in exact  mathematics. This leads to approximations as well as upper and lower bounds on the numbers that can be represented. Also, approximations can be the source of errors and deviations from the exact numerical answer. For instance, on a machine with only 3 digit precision, numbers like 22, 2.22, 0.110, 100, 177 can be represented. Now if you try to add 2 and 1000 instances of 0.11 , your sum would be 112 on this machine and this matches with the exact answer. Similarly, if you try to add 9 and 9 instances of 0.11, the answer on this machine would be 9.99, which matches with the exact answer. However, if you try to add 10 and 9 instances of 0.11 in that order i.e 10+0.11+0.11…., the machine would return 10 as answer because the moment you try to add 0.11 to 10, you are going to exceed the precision of the machine. Now imagine doing the same calculation in the reverse order i.e adding all the nine 0.11’s first and then 10 i.e. 0.11+0.11+….+10, the machine would return an answer of 0.99 which is far off from the actual answer 10.99 and far worse than the previous approximation of 10 (for the other order of addition). This means that the way you arrange your numbers( in memory, for instance an array) to be added also may influence the sum!! I wish that embedded systems engineers read more on this subject so that the numerical errors that we see cropping up in such systems get reduced. A nice introduction is at wikipedia.