Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Multiplying Matrices Without Multiplying

arxiv.org

Post reply on HN
Print view View original

111–120 of 124 posts

Re: Multiplying Matrices Without Multiplying

#111

Post by kazinator »

omegalulw wrote: post #109
kazinator wrote: post #51

Earlier quoted context omitted.

The angle and cosine start to lose their geometric intuition when we go beyond 3D. The concept of correlation has no issue with additional components. The concept of similarity of two 17-element vectors is clear. In fact correlation intuitively scales to "infinite component vectors": the dot product becomes multiplying two functions together and then taking an integral. The Fourier transform of a periodic signal is b…

Not really, for example, in physics, lines in 4D are just as meaningful as they are in 3D, more even (they are called geodesics). So are the angles between them. The real problem is that we just don't have good intuitions of higher dimensions in general.

I mean, I get that if I have, say:

  [0 1 1 1 0 1 0 0]
  [1 0 0 0 1 0 1 1]
that these are perpendicular to each other, which I will easily call ninety degrees, and that two such collinear vectors are at zero degrees.

But I somehow wouldn't go from that intuition into specific cosines. Like "Oh, look, if I divide out the lengths from the dot product, I'm getting 0.5! Why that's the cosine of 60 degrees!"

Re: Multiplying Matrices Without Multiplying

#112

Post by eesmith »

credit_guy wrote: post #110
eesmith wrote: post #71

Earlier quoted context omitted.

Checking Google Scholar, I found this 1962 paper by King titled "Table Look-Up Procedures in Data Processing" - https://dl.acm.org/doi/abs/10.1145/800198.806120 > It is not generally known that to provide seven- decimal accuracy of the sine function, allowing third-order interpolation, only 15 entries are required [*] ... The following commentary is interesting. > In spite of these developments in table construction,…

> It is not generally known that to provide seven- decimal accuracy of the sine function, allowing third-order interpolation, only 15 entries are required [*] ... That got me thinking: is that so? how do you do that? Luckily, scipy has all sorts of interpolation tools, so one can just experiment a little. Third-order interpolation -> that means cubic splines. How many points do you need for a cubic spline approximati…

How does that compare to the claim that only 15 points are needed?

I found the paper. https://archive.org/details/bitsavers_ibmproceedmputationSem... (Note the type: that paper starts on page 52; Krawitz also had another paper on page 66.)\

The "15 cards" is on page 56.

The paper uses Stirling's interpolation formula.

https://en.wikipedia.org/wiki/Brahmagupta%27s_interpolation_... notes that the Indian mathematician and astronomer Brahmagupta used a second-order version of the interpolation formula to compute a sine table in the early 7th century.

The Wikipedia page links to the Stirling interpolation function description at https://archive.org/details/introductiontonu00hild_0/page/13... .

It looks like it's also called Stirling’s Central Difference Formula.

Any chance you could work this out with scipy? My numeric abilities are pretty crappy.

Re: Multiplying Matrices Without Multiplying

#113

Post by bick_nyers »

ffast-math wrote: post #40

Primary author here. Happy to answer questions! Also, feel free to email me at the address in the paper if you're interested in talking about it in more detail. E.g., I've already heard from some hardware folks looking at expanding on this work.

Is there any significant performance gain for smaller matrices, such as 3x3 or 4x4? Video game engines do a lot of these

Re: Multiplying Matrices Without Multiplying

#114

Post by credit_guy »

eesmith wrote: post #112
credit_guy wrote: post #110

Earlier quoted context omitted.

> It is not generally known that to provide seven- decimal accuracy of the sine function, allowing third-order interpolation, only 15 entries are required [*] ... That got me thinking: is that so? how do you do that? Luckily, scipy has all sorts of interpolation tools, so one can just experiment a little. Third-order interpolation -> that means cubic splines. How many points do you need for a cubic spline approximati…

How does that compare to the claim that only 15 points are needed? I found the paper. https://archive.org/details/bitsavers_ibmproceedmputationSem... (Note the type: that paper starts on page 52; Krawitz also had another paper on page 66.)\ The "15 cards" is on page 56. The paper uses Stirling's interpolation formula. https://en.wikipedia.org/wiki/Brahmagupta%27s_interpolation_... notes that the Indian mathematician…

In my prior comment I used equidistant points for the interpolation.

In scipy you can use smoothing splines to get something close to optimal approximating splines with non-equidistant points. If you aim for a maximum error of 5e-8 (so when you round you have 7 exact decimal places), then with cubic splines you need 33 knots (including the ends). Now, the sine values are always less than one, so the digit before the decimal place is 0. If you count that towards accuracy, then you might be looking for an error not to exceed 5e-7, in which case scipy finds that you need 17 knots including the ends, so 15 interior knots.

    from scipy.interpolate import UnivariateSpline
    xs = np.linspace(0,np.pi/2,1000,endpoint=True)
    s = UnivariateSpline(xs,np.sin(xs),k=3,s=0.75e-11)
    ts = np.linspace(0,np.pi/2,10000)
    print("Max error: " , np.max(np.abs(s(ts)- 
       np.sin(ts))))
    print("Number knots: ", len(s.get_knots()))

    >> Max error:  4.761484727611176e-07
    >> Number knots:  17

Re: Multiplying Matrices Without Multiplying

#115

Post by Nevermark »

adwn wrote: post #89
Nevermark wrote: post #56

Earlier quoted context omitted.

It generalizes perfectly. The angle between two lines in any dimensions is the same concept. Two (non-collinear) lines share a plane. The angle on that plane is just the ordinary angle, no matter how many dimensions the two lines are embedded in. In the case they are collinear, the angle between them is zero on any plane that intersects them. So that corner case works too, regardless of numbers of dimensions.

> Two (non-collinear) lines share a plane. The angle on that plane is just the ordinary angle, no matter how many dimensions the two lines are embedded in. Okay, but now you've got a plane in n-dimensional space. How do you define/calculate the angle between the two vectors without falling back on the dot product? You could say: The angle between the two vectors A and B is defined as the smallest rotation around thei…

The normal vector is the cross product of the two vectors.

u = [u1 u2 u3] v = [v1 v2 v3]

in dimensions i, j, k

u x v = determinate of this matrix:

  =  | i  j  k|
     |u1 u2 u3|
     |v1 v2 v3|

  = (u2v3-v2y3)i - (u1v3 - v1y3)j + (u1v2 - v2u2)k

Re: Multiplying Matrices Without Multiplying

#116

Post by eesmith »

credit_guy wrote: post #114
eesmith wrote: post #112

Earlier quoted context omitted.

How does that compare to the claim that only 15 points are needed? I found the paper. https://archive.org/details/bitsavers_ibmproceedmputationSem... (Note the type: that paper starts on page 52; Krawitz also had another paper on page 66.)\ The "15 cards" is on page 56. The paper uses Stirling's interpolation formula. https://en.wikipedia.org/wiki/Brahmagupta%27s_interpolation_... notes that the Indian mathematician…

In my prior comment I used equidistant points for the interpolation. In scipy you can use smoothing splines to get something close to optimal approximating splines with non-equidistant points. If you aim for a maximum error of 5e-8 (so when you round you have 7 exact decimal places), then with cubic splines you need 33 knots (including the ends). Now, the sine values are always less than one, so the digit before the…

Thanks!

I wish I could find a published list of that table of 15 values.

In my search, I found https://www.jstor.org/stable/2002889?Search=yes&resultItemCl... which comments that an optimum interval table of sines and cosines for 7 place values has 2700 cards instead of 9000. "Each time this table is used, more than two hours of sorting and gang punching time is saved."

The only published "optimum interval table" I could find in archive.org was https://archive.org/details/dli.ernet.212891/page/149/mode/2... where table VII is the function f(r*2) = 1/r*3.

> This is the first time that such a table has ever been printed for use with a hand calculating machine. However, the computer will find that it is easier to use than an ordinary table which requires second difference interpolation, since no interpolating coefficients are needed; and it is not necessary to pay any attention to the irregular intervals.

One of the worked out examples is:

  r^2 = 4.043172
  F = (0.04686041 - 0.043172 x 0.01420874 ) x (-0.043172) + 0.124999851 
    = 0.12300327

Re: Multiplying Matrices Without Multiplying

#117

Post by robertlagrant »

kazinator wrote: post #98
setr wrote: post #97

Earlier quoted context omitted.

I believe he’s getting at the idea of nested levels of corruption, with no visibility into where that corruption happens (because recompilation of the compiler/ML produces a fresh inscrutable binary). I suppose the better term in this context is error propogation

It relates in the following way. Suppose you have some framework for calculation which depends on matrix multiplications. You use that framework to develop some approximation for matrix multiplications which are faster. Then to make that framework faster, you substitute that back into the framework. That is a sort of bootstrapping which user qsort has related to compiler bootstrapping. The goal in compiler boostrappi…

It's purely a performance increase. Its definition of valid will need to be that it matches the output of the non-ML version.

Re: Multiplying Matrices Without Multiplying

#118

Post by adwn »

Nevermark wrote: post #115
adwn wrote: post #89

Earlier quoted context omitted.

> Two (non-collinear) lines share a plane. The angle on that plane is just the ordinary angle, no matter how many dimensions the two lines are embedded in. Okay, but now you've got a plane in n-dimensional space. How do you define/calculate the angle between the two vectors without falling back on the dot product? You could say: The angle between the two vectors A and B is defined as the smallest rotation around thei…

The normal vector is the cross product of the two vectors. u = [u1 u2 u3] v = [v1 v2 v3] in dimensions i, j, k u x v = determinate of this matrix: = | i j k| |u1 u2 u3| |v1 v2 v3| = (u2v3-v2y3)i - (u1v3 - v1y3)j + (u1v2 - v2u2)k

That works for 3D space. What about n-dimensional vectors?

Re: Multiplying Matrices Without Multiplying

#119

Post by honie »

ltbarcly3 wrote: post #47
antonzabirko wrote: post #33

Earlier quoted context omitted.

I meant learning barrier. If i had the money i likely would go for it though!

I really don't know how to respond other than to say: "I would have done this years ago if I knew how to do it" is fantastically narcissistic.

I see where you are coming from, but I personally don't find the comment narcissistic: I read it the OP of the comment thinking out load, saying "ah! It's nice to know that I have thought about something similar, and someone made the effort to show that it works!".

Re: Multiplying Matrices Without Multiplying

#120

Post by coef2 »

kazinator wrote: post #98
setr wrote: post #97

Earlier quoted context omitted.

I believe he’s getting at the idea of nested levels of corruption, with no visibility into where that corruption happens (because recompilation of the compiler/ML produces a fresh inscrutable binary). I suppose the better term in this context is error propogation

It relates in the following way. Suppose you have some framework for calculation which depends on matrix multiplications. You use that framework to develop some approximation for matrix multiplications which are faster. Then to make that framework faster, you substitute that back into the framework. That is a sort of bootstrapping which user qsort has related to compiler bootstrapping. The goal in compiler boostrappi…

debugging a machine learning algorithm is already hard without this approximation method. I can see adding another layer could make it extremely harder.
Post reply on HN