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

71–80 of 124 posts

Re: Multiplying Matrices Without Multiplying

#71

Post by eesmith »

trilinearnz wrote: post #69
richrichardsson wrote: post #60

Earlier quoted context omitted.

I was using a precomputed table of sine values in 3D graphics way before Quake ever hit the scene, and I certainly didn't invent that idea either.

Ah that's useful to know that it was conventional up until then, thanks. It was my first exposure, personally :)

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 turned out two decades ago that the technology was such that table look-up was too slow for arithmetic. The stored-program type of machine displaced this approach. By this method the value of a function, such as sin x, is computed afresh every time. One cannot but wonder how many times such a number has been re-computed in the last decade, and inquire whether technological developments may make tables efficient again.

> Over the years the emphasis in machines has slowly changed from the central processing unit to memory. From the point of view of table look-up, the memory is the central feature of a machine. Indeed the central processing unit is unnecessary.

The [*] is Krawitz. E., "Proc. Industrial Comp. Seminar," IBM, p. 66, 1950. I cannot find this publication with only a simple search.

See also https://scholar.google.com/scholar?as_sdt=0%2C5&as_yhi=1990&... which finds titles like "A rapid lookup table method for trigonometric functions" (1982) at https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801210... .

Re: Multiplying Matrices Without Multiplying

#72

Post by EVa5I7bHFq9mnYK »

trilinearnz wrote: post #19

Clever and logical. It reminds me of when John Carmack used a precomputed table of Sine values for fast lookup in Quake, rather than running the actual function on the CPU.

Long before Carmack, a precomputed table of cosine values has been used in a vacuum-tube based surface-to-air missile system I have been maintaining. The table consisted of only one element: 0.7, i.e. the cosine of any angle was considered 0.7. Somehow, it was good enough for intercepting jet fighters and saved a lot of vacuum tubes.

Re: Multiplying Matrices Without Multiplying

#73

Post by EVa5I7bHFq9mnYK »

trilinearnz wrote: post #69
richrichardsson wrote: post #60

Earlier quoted context omitted.

I was using a precomputed table of sine values in 3D graphics way before Quake ever hit the scene, and I certainly didn't invent that idea either.

Ah that's useful to know that it was conventional up until then, thanks. It was my first exposure, personally :)

I am old enough to remember printed books in the library that contained pre-computed tables of logarithms, sines and other common functions.

Re: Multiplying Matrices Without Multiplying

#74

Post by thesz »

kazinator wrote: post #51
xyzzyz wrote: post #37

Earlier quoted context omitted.

The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.

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…

Word2vec with embedding size 300 and more do refute your claim. I successfully trained word2vec model with above embedding sizes and used inner product similarity to create word clusters as it is out of the box there. Then I made a clusutering language model and got significantly lower perplexity compared to word-based language model.

Re: Multiplying Matrices Without Multiplying

#76

Post by michelpp »

infogulch wrote: post #36

I wonder how much alternative number representations have been studied for use in matrices. Like, storing the log of values instead so that multiplication can be done by just adding. Or something like Zech's logarithm. Or even, take the log of whole matrices (which is a thing apparently [0]), then adding them to compute their multiplication. I wonder if the logarithm of a matrix can be computed using ML. [0]: https:/…

There is a logarithmic semiring:

https://en.wikipedia.org/wiki/Log_semiring

which can be used to multiply two sparse matrices with the GraphBLAS. here is an example in Python:

https://github.com/Graphegon/pygraphblas/blob/main/demo/Log-...

Re: Multiplying Matrices Without Multiplying

#77

Post by antonzabirko »

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.

What? No im saying it's one of the ideas i worked on before i switched away from the field...?

Re: Multiplying Matrices Without Multiplying

#78

Post by atq2119 »

10000truths wrote: post #70
atq2119 wrote: post #68

Earlier quoted context omitted.

The variance goes to 0 only if you normalize, which is to say that two random high-dimensional vectors are very likely to be close to orthogonal (under mild assumptions on their distribution). I agree that that's one of those important but initially unintuitive facts about high dimensions. Just like almost all of the volume of a reasonably round convey body is near its surface. But it also doesn't really contradict t…

> Just like almost all of the volume of a reasonably round convey body is near its surface. I’d say that’s pretty intuitive for anyone who can see a pattern in surface area to volume ratios. 1D ball: 2 / (2 * r) = 1/r 2D ball: (2 * pi * r) / (pi * r^2) = 2/r 3D ball: (4 * pi * r^2) / (4/3 * pi * r^3) = 3/r nD ball: ... = n/r

Most people don't find arguing from formulas intuitive unless the formulas themselves are intuitive. If you truly believe they are, I'd be curious to know why.

Re: Multiplying Matrices Without Multiplying

#79

Post by arthur2e5 »

esjeon wrote: post #25

> MADDNESS I think this name really fits well to the concept. Replacing matrix-multiplication with some hash-lookups! (warning: an overly simplified statement) This is a really interesting application of PQ(product quantization), which itself also requires learning (usually K-means). Paper: https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_wi... Considering that ANN has survived through many approximations (e…

Certainly off topic, but gotta say I prefer “MADDLESS” over “MADDNESS” for being more… obvious. It still sounds close enough to me, but again I might be just letting my Southern-Chinese ear loose with the n/l confusions…

Re: Multiplying Matrices Without Multiplying

#80

Post by amelius »

noobermin wrote: post #14
TrainedMonkey wrote: post #4

Earlier quoted context omitted.

Ironic thing is large part of how ML works is via matrix multiplication.

It important to remember dense matrix multiplication (doing it by hand) is a O(N^3) operation, this is about approximations to multiplication that beat that already harsh complexity. There is a whole field that develops approximations to matrix multiplication of large matrices, I'm assuming this article is about using ML to find good approximations. To the replies, the very act of evaluting a prediction from a NN is…

But ML relies on GPUs with lots of parallelism, so e.g. O(N^3) becomes O(N^2) for N smaller than the number of cores (roughly speaking).
Post reply on HN