4 ms·
How would one go about finding new ways to multiplicate matrices? Trial and error? Can the process be automated? Genius gets hit on the head by an apple moment
by Traubenfuchs 4y ago
How would one go about finding new ways to multiplicate matrices?
Trial and error? Can the process be automated? Genius gets hit on the head by an apple moment?
- klyrs 4y agoFor small n, you can reasonably brute-force all (n x n) multiplication formulae in characteristic 2 because there's a naive bound on the number of element multiplications and the coefficients are binary. As n gets large (say, n>3?), the cost of brute-force becomes prohibitive. Beyond brute-force, I imagine that this problem could be phrased as a max-sat problem, mixed-integer linear program or similar. There are generic solvers that can get solutions for problems of moderate size. But unless it's a fairly rote translation to the solver's native representation, it's often better to write a custom solver and port heuristics into the notation native to the problem. As far as I understand it, that's the approach that the Fawzi et al and TFA took.
- js8 4y agoI was wondering, why use Deepmind when you can just use SAT solver? I am not saying SAT solvers cannot be improved with AI, maybe they can.
- klyrs 4y agoNote my uncertainty about the suitability of a max-sat formulation. But also note who did the Fawzi et al result: the DeepMind team at Google. I think that dogfooding their own stuff is an understandable default.
- fcholf 4y agoActually, this has been done: https://arxiv.org/abs/1903.11391 https://arxiv.org/abs/1903.11391
- Jabbles 4y agoSee https://news.ycombinator.com/item?id=33096580 https://news.ycombinator.com/item?id=33096580
- whymauri 4y agoVirginia Williams teaches an excellent course: https://people.csail.mit.edu/virgi/6.890/ https://people.csail.mit.edu/virgi/6.890/ Lecture notes are open.
- PartiallyTyped 4y agoThank you for sharing this! Do you know of similar gems?