20 ms·

Matrix multiplication inches closer to mythic goal

• melling 6y ago
  I am doing Andrew Ng’s ML Coursera course with Matlab. I’ve now got the crazy desire to see matrices and vectors built into every language in a clean and succinct way.
  • taxemeEvasion 6y ago
    It's a main reason why Fortran still has such a hold on the SciComp/HPC community.
    • gowld 6y ago
      Fortran is also optimized and debugged over decades of testing.
      • karma_fountain 6y ago
        Yeah those algorithms are numerically tested, haven't changed in years, and really fast. You can certainly get to convenient matrix manipulation in C++, but then your compile times will increase significantly.
        • Zardoz84 6y ago
          You can have a fast implementation and fast compilation time with DLang
        • andi999 6y ago
          Performance might be worse in c++
        • DesiLurker 6y ago
          Can the fortran implementations do auto-vectorization on simd hardware? or map to gpu using cuda-like library? not rhetorical, genuine question.
          • cygx 6y ago
            Yes. See e.g. https://gcc.gnu.org/projects/tree-ssa/vectorization.html#example6 https://gcc.gnu.org/projects/tree-ssa/vectorization.html#exa... https://developer.nvidia.com/cuda-fortran https://developer.nvidia.com/cuda-fortran
          • jhayward 6y ago
            Yes, in fact all the original research for those things was done in Fortran compilers.
          • TheRealKing 6y ago
            Fortran is a fully-vectorized and parallelized language at all levels, from instructions to shared and distributed parallelism (corresponding to one-sided MPI communications). This has been the case for at least 3 decades if not more. There are mature GPU support for Fortran. NVIDIA and PGI are currently implementing the standard parallel features of Fortran via GPUs.
  • tasty_freeze 6y ago
    One of the unexpected things is Dartmouth BASIC from 1964 had matrix primitives, despite being an otherwise primitive language. MS never took up the feature, but I know Wang BASIC did on their 2200 family of machines. For example: 10 DIM A(3,3),B(3,3),C(3,3) 20 MAT READ A 30 DATA 1,-5,7, .45,23,9, -5,-1,0 40 MAT B=A:REM assignment 50 MAT B=ZER:REM zero array 60 MAT B=CON:REM all 1s 70 MAT B=IDN:REM identity 80 MAT B=TRN(A):REM transpose 90 MAT B=(2)*A:REM scale 100 MAT B=INV(A),D:REM invert array, determinant in scalar D 110 MAT C=A*B:REM matrix multiplication 120 MAT PRINT C:REM prints something close to an IDN array
    • coliveira 6y ago
      Believe it or not, engineers were heavy users of BASIC in the first few years. And FORTRAN was created with the notion of matrix multiplication, so it was just natural that BASIC implementations supported matrix multiplication.
      • pavlov 6y ago
        My grandfather was a construction engineer. I remember visiting his office around 1990 just before he retired. His only computer was a Commodore 64 and he had written all the software himself in BASIC over the years, just translating a lifetime of professional experience into these little interactive programs on floppies. Maybe the modern equivalent would be to use Excel.
    • Someone 6y ago
      The first version of Dartmouth basic ran on a system with a whopping 20kB of memory (8k words at 20 bits each. See https://en.)wikipedia.org/wiki/GE-200_series https://en.)wikipedia.org/wiki/GE-200_series) The GE-635 (https://en.wikipedia.org/wiki/GE-600_series https://en.wikipedia.org/wiki/GE-600_series) that it ran on most of its life could have 4 CPUs, had protected memory and floating point hardware, and supported at least 200 kilowords of memory (http://www.bitsavers.org/pdf/ge/GE-6xx/CPB-371A_GE-635_System_Man_Jul64.pdf http://www.bitsavers.org/pdf/ge/GE-6xx/CPB-371A_GE-635_Syste...) At 36 bits/word, that’s 900 kilobytes. The first version of Microsoft basic (https://en.wikipedia.org/wiki/Altair_BASIC https://en.wikipedia.org/wiki/Altair_BASIC) ran in 4 kilobytes (leaving about ¾ kilobytes for programs and data), so it’s understandable that it lacked some features (it didn’t even have else clauses in if statements, had SIN, but not COS or TAN, didn’t support integer or string variables, etc))
  • montalbano 6y ago
    Convenient matrix algebra is one of the selling points of Julia.
    • nerdponx 6y ago
      I'm really hopeful that Julia will continue to gain adoption. That said, I would love to have good data science library support (bindings to stuff like BLAS/LAPACK, Torch, Stan, etc) in Idris. Imagine vector and matrix dimensions checked at compile time. Probabilities guaranteed to be between 0 and 1, checked at compile time. Compile-time enforcement that you are handling "nil/null" data inputs correctly when reading data from a database or CSV file. Writing a web scraper with linear types to help catch bugs & performance leaks. Maybe even proving theorems about the math code you're writing ("is this a valid way to express X"?). Maybe not ideal for rapid exploratory model development, but it'd be pretty damn cool for writing data science tooling/libraries and "production" ML code in my opinion.
      • deleted 6y ago
        [deleted]
      • Ericson2314 6y ago
        Looking forward to Dependent Haskell for linear algebra, and seeing what existing stuff can be retrofit.
      • kristjansson 6y ago
        Not that it has bindings to other tools, but it sounds like Dex[1] would be relevant to your interests! [1]: https://github.com/google-research/dex-lang https://github.com/google-research/dex-lang
  • centimeter 6y ago
    Beyond matrices and vectors, it would be nice to have generalized (typed) tensors. What you can do with matrices alone is really somewhat limited.
    • Robotbeat 6y ago
      From a data structure perspective: You mean like an n-dimensional array? That’s what Matlab does. Matrices (2D arrays) are just a special case of array in Matlab.
      • whimsicalism 6y ago
        I suspect by the usage of the phrase "typed" they mean something like that, but where the axes/dimensions/whatever you call them are typed - ie. you can't naively take a product along the time dimension of A with the batch dimension of B.
        • jpeloquin 6y ago
          xarray seems to fit the bill. As long as you're ok with runtime axis/dimension/type checking. https://xarray.pydata.org/en/stable/ https://xarray.pydata.org/en/stable/
          • whimsicalism 6y ago
            I've explored this space a bit, and I don't think the perfect solution is here yet. In my view, static checking should be the goal. It's harder to iterate quickly when your network dynamically fails 30 layers later due to some edge case where you forgot to take a transpose. Definitely much better than it silently succeeding if the dimensions happen to be the correct size though! https://github.com/deepmind/tensor_annotations https://github.com/deepmind/tensor_annotations seems promising. I've developed a mypy plugin for pytorch that does similarly off of the "Named Tensor" dynamic feature (which isn't well supported yet), but haven't released it yet. I'm also excited by the ways in which including this in some sort of "first-class" way could make tensor semantics simpler, which I'm assuming xarray allows? Many of the operations enabled by http://nlp.seas.harvard.edu/NamedTensor http://nlp.seas.harvard.edu/NamedTensor are quite nice and similar ideas can let you write more generic code (ie. code that works automatically for on tensors with and without a batch dimension)
  • bobbybabylon 6y ago
    Have you looked at languages like J or APL?
  • make3 6y ago
    Yes, have you tried Julia? It is pretty much how you describe. There are other things that I don't like about that language, but the matrix part is really great
  • mkaic 6y ago
    Just finished the course and couldn't agree more. Everything seemingly is faster with matrices!
  • teruakohatu 6y ago
    The base type in R is a vector. A number such as 3.14 is simply a vector of length 1. So functions are vectorized by default (as long as you don't do any operations that are explicitly not vectorizable). Once you get your head around everything being a vector, R can be a lot of fun. I love Julia but I wish I didnt need to explicitly broadcast functions across a vector.
    • cbkeller 6y ago
      I was annoyed by that at first, but eventually came to appreciate how Julia's semantics for when broadcasting is or is not required for operations on scalars, vectors, and matrices map to the underlying math. I.e., for an N x N matrix `A` 5 * A does not require broadcasting because multiplication of a matrix by a scalar is mathematically well-defined, whereas 5 + A (assuming you want element-wise addition) does require broadcasting, i.e., 5 .+ A because addition of a vector and a matrix is not mathematically well-defined.
      • teruakohatu 6y ago
        I do understand why they do it, and numpy can play a bit fast and loose which can be confusing, but I miss reading elegent vector-by-default R code. The Julia approach also has some drawbacks, I was writing some code the other day and forgot to broadcast exp() across a matrix. exp(A) and exp.(A) gives very different results but it's not immediately obvious looking at code, especially when the code is a mixture of broadcasted and native matrix function calls which dots peppered all over the place.
        • eigenspace 6y ago
          Well, again I'd say that's just like the above examples. The exponential of a (square) matrix is indeed a very well defined object [1] with semantics perfectly consistent with the exponential of a scalar. On the other hand, broadcasting exp over a matrix is a very different operation, which doesn't really have any meaning in a linear algebra sense. I understand it's an easy mistake to make when you're used to R or Numpy, but I'd say it's their fault you're making this mistake, not Julia's. [1] https://en.wikipedia.org/wiki/Matrix_exponential https://en.wikipedia.org/wiki/Matrix_exponential
• yrral 6y ago
  Does anyone know how matrix multiplications are implemented in CPUs GPUs or ML asics? Are there optimizations used or do the optimizations take too much circuitry and thus the n^3 method is still used?
  • OneDayIGoHome 6y ago
    For GPUs, it's actually much faster than O(n^3) because computing each entry in the result matrix is independent. Hence, the problem is embarrassingly parallel in a way. I don't know how to use O() notation for GPUs but it should be something like O(n^2/k^2) where K is the tile size [0]. Also lower memory bandwidth becomes a bottleneck here. So there is a lot of optimizations done on how to transfer from CPU to GPU and then within GPU to efficiently query the matrices. [0]https://docs.nvidia.com/deeplearning/performance/dl-performance-matrix-multiplication/index.html https://docs.nvidia.com/deeplearning/performance/dl-performa...
    • colanderman 6y ago
      O notation doesn't apply to hardware in that way. The naive algorithm is still O(n^3) on a GPU. Remember that O notation is concerned with behavior at the limits and ignores constant factors. Parallel hardware can only provide a constant speedup for problems of arbitrary size, hence it does not show up in O notation.
      • anon_tor_12345 6y ago
        r/confidentlyincorrect complexity is wrt a particular model of computation - a turing machine. turing machines are sequential (NTMs aren't). run time on a parallel model is not necessarily a constant off from run time on a sequential model.
        • colanderman 6y ago
          Snark aside, GP is asking about GPUs. GPUs are not nondeterministic Turing machines.
• JulianChastain 6y ago
  The article doesn't specify, and I don't have the prior knowledge to understand the paper; Is there a coded implementation of this in some language or is it purely a mathematical description of how theoretically multiplication can always be done with slightly fewer multiplications?
  • ovi256 6y ago
    I think the way it'll go is: it'll be implemented in Fotran, BLAS and so on until it percolates to numpy / CUDA so mortals like us can use it.
    • MPSimmons 6y ago
      Agree. I don't think we'll notice, but the next gen of CUDA will be better because of it.
      • amluto 6y ago
        These particular algorithms tend to have large Constance factors, so you need astronomically large matrices before they become faster than algorithms with worse exponents but better constant factors.
        • ovi256 6y ago
          Hopefully the matmul implementation can check matrix size and pick the algorithm to use from that. I think some may already do this.
  • nonameiguess 6y ago
    Strassen's algorithm is still the fastest to be widely implemented. The Coppersmith-Winograd variants that have achieved better asymptotic complexity are all galactic algorithms: https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm.
  • sdenton4 6y ago
• vessenes 6y ago
  Man, Quanta magazine is a gift. I love that there is a publication with a significantly higher reading level assumed than most pop science content, but not written for industry insiders, it’s just great. I pitched them a paper magazine a few years ago, because I wish I could leave these around for my kids to flip through, but no joy yet..
  • coliveira 6y ago
    You now mentioned something important: older generations have left behind journals, magazines, books, all kinds of documents that represent their generation. When our generation is gone, there will be very little physical traces left. Someone will have to search archive.org or similar to find anything.
    • mjburgess 6y ago
      It's the function of historians to do the archeology and summarise for a broader audience.
      • goatinaboat 6y ago
        It's the function of historians to do the archeology and summarise for a broader audience Those summaries will be written in a similarly ephemeral format. A book in a library can sit there and be rediscovered in a hundred years. A scroll or an engraving in a thousand. But we create things that have evaporated in a mere decade.
        • Robotbeat 6y ago
          I’ve been thinking of backing up a few dozen megabytes of my most important files in like QR codes or maybe something simpler like dual-parity data matrix with instructions in plain text and printed out FORTRAN code. Printed on long lived (waterproof?) paper with a laserjet. Along with plain text printouts of text and pictures. Even thought of etching that on stainless plates or something. Could be scanned with a smartphone or even decoded by hand (include an ASCII lookup table).
• ovi256 6y ago
  > “Exponent two” refers to the ideal speed — in terms of number of steps required — of performing one of the most fundamental operations in math: matrix multiplication. If exponent two is achievable, then it’s possible to carry out matrix multiplication as fast as physically possible. Can anyone clarify what "as physically possible" means here? Are there physical systems that perform matrix multiplication in O(n^2) ? (I feel silly even asking that about a physical, non-computation system) I remember there were applications of optical computation, including a startup that wanted to accelerate deep network inference through optical computation: they had a way to do matrix multiplication using a projector (for the data matrix) and a 3D printed lens (for the network weights).
  • sdenton4 6y ago
    I don't think the sentence is very good. You need n^2 time just to read the two matrices, so I always thought of that as a natural lower bound. (Of course, we're talking about multiplications eventually here, so may not be exactly what they meant...)
    • deleted 6y ago
      [deleted]
  • jwmerrill 6y ago
    I don’t think they’re actually intending to refer to physics here—they could have said “as fast as theoretically possible” instead. A square matrix with n rows and columns has n^2 entries, so if you need to look at all the entries in two matrices to compute their product, then you need to do O(n^2) work just to look at all the relevant entries. The only way you could get around this is if you know many entries are 0, or identical, or have some other structure such that you don’t need to look at them separately.
    • fastball 6y ago
      I don't think they're talking about total operations here, as pointed out in the article this is just about the number of multiplications. Every matrix multiplication can be boiled down to multiplying rows by columns. This is definitionally required for matrix multiplication, so that is the lower bound for how many multiplications are required. One multiplication for every final element in the n x n matrix, or n^2.
• joosters 6y ago
  Shouldn't that first graph have the axes the other way round? Time (date) should be on the x-axis, and the measurement on the y-axis? As it is, it looks terribly confusing to me.
• CalChris 6y ago
  If n^2 is possible then it would be possible for a given n, say 4. Can't it be shown by example or exhaustive search that this is or isn't possible for 4?
  • dragontamer 6y ago
    O(n^2) is a scaling factor: what happens as n->infinity. An optimal arrangement for n==4 already exists. Both AMD MI100 and NVidia Volta / Ampere perform 4x4 FP16 matrix multiplication in a single assembly language statement. An 8x8 matrix is just an arrangement of four 4x4 matricies (!!!!). As such, you can define a 8x8 matrix multiplication as a 4x4 matrix multiplication over 4x4 matricies. This recursive relationship is often key to how they manage to get faster-and-faster. Getting to O(n^2.8), or O(n^2.6,) etc. etc.
  • kadoban 6y ago
    Since we're looking for a O(n^2) algorithm, not specifically n^2 operations, this actually doesn't help. You could for example need 1000n^2+1000000 operations, which would look terrible if you only look at n=4, but you're golden if n=10000000 (and even if there's no practical n where you win, it's still theoretically very interesting).
• fastball 6y ago
  > no, no, no, no, no Confirmed Strassen thinks the lower bound is n^2.32192809489.
  • lsb 6y ago
    log2(5)???
• deleted 6y ago
  [deleted]
• woopwoop 6y ago
  On the off chance an expert reads this comment and feels like answering, is there a consensus opinion (or even just your opinion) on what the best result is likely to be? Do people think O(n^2) is actually possible? Edit: shoulda read to the end, it says that Strassen says no.
  • phkahler 6y ago
    I'm no expert, but IMHO it feels like a problem that might have O(n^2 log(n)) time complexity. That would be more satisfying than some arbitrary non-integer exponent.
    • waynecochran 6y ago
      Get that n out of the exponent -- that is waay too slow. Maybe you meant O(n^3*log(2))? That exponent is definitely a constant.
      • btilly 6y ago
        We have better than that. I think that what was meant is O(n^2*log(n))
        • nightcracker 6y ago
          That isn't just what's meant, that's also what's written.
          • btilly 6y ago
            The way that it was written didn't disambiguate whether or not the log is part of the exponent. Putting the * in there disambiguated that.
            • nightcracker 6y ago
              It doesn't. The multiplication is implied and it would have the same precedence as explicitly putting * there. So either both are ambiguous or neither is (and it isn't, the poster was just mistaken).
• jvanderbot 6y ago
  What is with that banner image? Time on the Y axis? Factor on the X? Some mythical line-fit of factor over time that doesn't match the data? Great article though. Yuck.
  • daureg 6y ago
    I felt the same about that picture, the original source is less pretty but much easier to read: https://commons.wikimedia.org/wiki/File:MatrixMultComplexity_svg.svg https://commons.wikimedia.org/wiki/File:MatrixMultComplexity...
  • black_puppydog 6y ago
    Came here for exactly that. WTF?
  • 1-more 6y ago
    It made me think of the progression of men's 100m dash times. I was really hoping it would line up better. I think long jump might have been a better choice for a spurious correlation graph. https://imgur.com/a/5quyLWC https://imgur.com/a/5quyLWC
    • 1-more 6y ago
      I think I cracked it: it lags about 30 years behind the long jump progression https://imgur.com/a/YHvXq7G https://imgur.com/a/YHvXq7G
  • ziddoap 6y ago
    I definitely agree, but thinking about it I wonder if it was simply to get a "gut reaction" to the graphic - that things are getting better and we are reaching the limit of what is possible (in the context of matrix multiplication). It's easier to get that feeling at a glance when the graphic is increasing left-to-right. With normal conventions the graphic would be decreasing. Which of course, that's what it is doing (and the goal). But the "gut reaction" to a decreasing graph is "things are doing worse". The gut reaction to graph increasing is "things are doing better". I could be completely off-base, but that's the only reason I can think of to eschew normal axis conventions.
• foolinaround 6y ago
  quanta magazine has been the best find for me this year!
• dekhn 6y ago
  in the time spent improving matrix multiplication by a tiny incremental amount, many gigawatt hours have been spent making existing CPUs, GPUs, and TPUs do matrix multiplication using far less efficient algorithms. It's unclear this work would really be important in production computing (I understand the theoretical desire) compared to time spent making other things work better.
  • snapcore 6y ago
    I was under the impression the Strassen method was rarely used because it has a number of drawbacks such as harder to parallelize, uses more memory, has bigger constants for complexity, less stable, etc. It's not really designed to be optimal for the current hardware, but just to lower the number of steps. It could be more useful in the future though.
  • MauranKilom 6y ago
    > It's unclear this work would really be important in production computing It most certainly won't [0]. But neither will something like 99% of mathematical research right now. [0]: See first example in https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm
• deleted 6y ago
  [deleted]
• dewiz 6y ago
  How would one calculate the $$$ value of exp2 multiplication? Eg if one finds a way, would it be worth keeping it a secret and creating a business around it?
  • hypersoar 6y ago
    First of all, you couldn't. The "fastest" multiplication algorithms for Matrix multiplication, which are roughly O(n^2.3), aren't used in practice. They're "galactic algorithms" (a term I just now learned), meaning that the size the problem would need to be for them to overtake the more common O(n^2.8) algorithm is too large for today's computers. O(n^2) might be theoretically valuable but practically useless. Second of all, algorithms aren't patentable. The only way to keep it exclusive would be to keep it secret. I can't think of any examples of a private company making a major scientific or mathematical breakthrough and then keeping it secret long enough to profit off of it.
    • desertrider12 6y ago
      > algorithms aren't patentable I wish. The RSA cryptosystem was patented and under license until 2000 in the US, even though the math wasn't secret.
    • ben509 6y ago
      > Second of all, algorithms aren't patentable. Algorithms absolutely are patentable because they are computing "machines." It's mathematical equations that aren't patentable, because they're closer to laws of nature.
• ur-whale 6y ago
  A graph with time on the Y axis ... a.k.a why make things simple when you can instead confuse 80% of your readership with a simple mirror trick.
  • tooltower 6y ago
    This is a common convention for annotating historical timelines. Even completely unrelated fields like Relativity routinely places time on the y-axis. Please take your snark elsewhere.
    • mschuetz 6y ago
      It is kind of weird and unintuitive. This one here, posted by another commenter, is much much more understandable: https://commons.wikimedia.org/wiki/File:MatrixMultComplexity_svg.svg https://commons.wikimedia.org/wiki/File:MatrixMultComplexity...
      • the8472 6y ago
        The WP image has an unfortunate offset on the Y axis, giving the impression that we're much closer to optimal than we actually are.
        • stephencanon 6y ago
          We don’t know this. I think a lot of people expect that there’s an O(n^(2+eps)) algorithm for any epsilon > 0, but that’s conjecture; we might already be at the optimum.
      • cmarschner 6y ago
        It is only unintuitive if your mental representation of time flows to the right. We all create a mental model of time at some point in our life, and then stick to it - often without ever talking about it to anyone. But the representations vary substantially between people. Many people might have a timeline where the past is on the left and the future is on the right - maybe along the reading direction. But for some, future expands to the left. For others, future expands in front of them while the past is behind them (quite inconvenient). It can make for a great party conversation to explore each others‘ timelines. If there are parties, that is.
• ableal 6y ago
  Is anyone looking into the memory accesses for the operation? Fifty years ago multiplication was vastly slower than RAM access. Nowadays it's pratically free compared to even getting data out of cache ...
  • MauranKilom 6y ago
    Nobody is remotely looking at running these algorithms in the real world. These are very much asymptotic complexities, and to draw benefit from even the 1990 version you'd have to literally use galactic input sizes. None of this is about making the matrix multiplications on your PC faster. https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
    • soVeryTired 6y ago
      Wikipedia says Strassen's algorithm is useful for n > 100 and is implemented in BLAS [0]. AFAIK Coppersmith-Winograd is more of a theoretical advance. Edit: ah, we're probably talking about the same thing. Strassen was 1970. [0] https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Sub-cubic_algorithms https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
• throwaway34u29 6y ago
  Huh, it's been along time since I heard the name Josh Alman. Last time I heard about him he was cheating in academic trivia. Looks like he's managed to contribute more positively to society since then.
• pjsg 6y ago
  There are related problems in computer science -- e.g. how quickly can you multiply a pair of 65536x65536 extended double precision matrices together. Note that each matrix consume ~68GB of memory, so you need (probably) at least 200GB to store the two input matrices and the output matrix. So far, so good. Now you want to see how fast it can really go if you are prepared to spend (say) $100k on the hardware (e.g. 64 times as many CPUs with some fancy interconnect fabric). How about spending $100M? It turns out that moving all this data around is also quite costly.....
  • goldenkey 6y ago
    That's not a problem in C.S. That's a problem in engineering.
    • BobbyJo 6y ago
      Until hardware can do everything free and instantly, making computations cheaper and faster will be a core problem in CS. Everyone enjoys when the hardware gives free gains though :)
      • goldenkey 6y ago
        C.S is not concerned with the fastest speed that off the shelf hardware can multiply two matrixes measured in seconds. You must be thinking of Linus Tech Tips.
        • BobbyJo 6y ago
          It is concerned with the lowest complexity method of doing so, which is directly related.
          • goldenkey 6y ago
            Tangentially, not directly. Algorithms become different beasts when implemented on real-world hardware.
• thomasahle 6y ago
  If you are interested in how those tensor methods work, the authors have another very nice paper that gives a great introduction https://arxiv.org/abs/1810.08671 https://arxiv.org/abs/1810.08671 It is actually not that different from Strassen after all. It just uses a bit more notation to help construct more clever ways of saving multiplication.
  • Const-me 6y ago
    I’m more interested why saving multiplications at the cost of more add/subtract helps overall? On all modern CPUs their speed is the same for float numbers. Specifically, they have 4 cycles of latency on Skylake, 3 cycles of latency on Zen2, throughput (for 32-byte vectors) is 0.5 cycles for both CPUs.
    • lapinot 6y ago
      My guess: general software multiplication is usually costlier than addition: it will pay off if you go for divide-and-conquer and your items are themselves matrices, or if they are arbitrary precision integers, or fractions, or elements of any ring really.
    • thomasahle 6y ago
      You actually save additions too. If you look at Strassens algorithm [1] you see that it splits each matrix in 4 blocks. Naively you can do 8 multiplications of those blocks, as well as 4 matrix additions, and recover the full matrix multiplication. If T(n) is the number of operations (additions as well as multiplications) for an nxn matrix multiplication, we can write the equation T(n) = 8T(n/2) + 4(n/2)^2. If we solve this, we end up with T(n) ~ n^3, which is of course the time complexity of naive matrix multiplication. However, with Strassen you end up with 7 smaller matrix multiplications and 18 matrix additions. The equation we get now is T(n) = 7T(n/2) + 18(n/2)^2. We end up with T(n) ~ n^(2.8). We see that when we save _matrix_ multiplications we eventually end up saving both elementary multiplications _and_ additions. [1]: https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm
    • Delk 6y ago
• balefrost 6y ago
  However, the number of additions required to add those sets of matrices is much closer together. Generally, the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices. Maybe my linear algebra is REALLY rusty, but I that doesn't seem right to me. For two 4x4 matrices, each element in the output matrix will be the sum of four products. So each of the 16 output elements will require 3 additions, and you'll need a total of 48 additions. I'm not sure where they're getting "16 additions" from. To multiply two nxn matrices according to the textbook method, I think you'll need n^3 multiplications and n^3-n^2 additions. I don't doubt that the multiplication time dominates the algorithm. Maybe this is just a nitpick.
  • soVeryTired 6y ago
    They're counting the additions needed to add the matricies, not to multiply them. The point being that matrix addition is order n^2 so even if you need to do a large number of matrix additions in some intermediate calculation, they don't hurt you as n gets large if you're trying to speed up matrix multiplication.
    • balefrost 6y ago
      That doesn't seem to be what they are saying. Here's the first sentence of the paragraph that I had originally quoted: As matrices grow larger, the number of multiplications needed to find their product increases much faster than the number of additions. The whole paragraph is talking about the multiplications and additions needed to find the product of two matrices.
      • afiori 6y ago
        it could refer to matrix multiplication and matrix addition of smaller matrices during the algorithm (iirc most fast multiplication algorithms start by splitting the matrix in pieces)
• failwhaleshark 6y ago
  Prepress paper: https://arxiv.org/pdf/2010.05846v1.pdf https://arxiv.org/pdf/2010.05846v1.pdf
• CoryOndrejka 6y ago
  Related to separate paper on using a different method for linear equation solving from a few weeks ago https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/ https://www.quantamagazine.org/new-algorithm-breaks-speed-li... seems likely if you can use a different method for solving linear equations, it may be that some matrix multiplication can also be improved using a different method.
• The_rationalist 6y ago
  are there any non-galactic (practical) algorithm faster than strassen (for non-small dense matrices) ?