## Introduction

Matrix multiplication occupies a central role in scientific computing with an extremely wide range of applications. Many numerical procedures in linear algebra (e.g. solving linear systems, matrix inversion, factorizations, determinants) can essentially be reduced to matrix multiplication [5, 3]. Hence, there is great interest in investigating *fast matrix multiplication *algorithms, to accelerate matrix multiplication (and other numerical procedures in turn).

SuanShu was already the fastest in matrix multiplication and hence linear algebra per our benchmark.

SuanShu v3.0.0 benchmark

Starting version 3.3.0, SuanShu has implemented an advanced algorithm for even faster matrix multiplication. It makes some operations 100x times faster those of our competitors! The new benchmark can be found here:

SuanShu v3.3.0 benchmark

In this article, we briefly describe our implementation of a matrix multiplication algorithm that dramatically accelerates dense matrix-matrix multiplication compared to the classical IJK algorithm.

## Parallel IJK

We first describe the method against which our new algorithm is compared against, IJK. Here is the algorithm performing multiplication \(C = A\times B\) for \(A\) is \(m\times n\), \(B\) is \(n\times p\), and \(C\) is \(m\times p\):

1 2 3 4 5 6 7 |
for (i = 1; i < = m; i ++){ for (j = 1; j <= p; j ++){ for (k = 1; k <= n; k ++){ C[i,k] += A[i,j] * B[j,k]; } } } |

In Suanshu, this is implemented in parallel; the outermost loop is passed to a ParallelExecutor .

As there are often more rows than threads available, the time complexity of this parallelized IJK is still roughly the same as IJK: \(O\left(mnp\right)\), or cubic time \(O\left(n^3\right)\) for \(m = n = p\). This complexity is not most desirable.

The core of our new multiplication algorithm, the Strassen algorithm, reduces the time complexity to \(O\left(n^{\log_27}\right)\).

## Strassen’s Algorithm

The Strassen algorithm [6] is based on the following block matrix multiplication:

\(\displaystyle \begin{pmatrix}A_{11} & A_{12}\\ A_{21} & A_{22} \end{pmatrix}\begin{pmatrix}B_{11} & B_{12}\\ B_{21} & B_{22} \end{pmatrix}=\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22}\\ A_{21}B_{11}+A_{22}B_{21} & A_{21}B_{12}+A_{22}B_{22} \end{pmatrix}\)

The naive method of completing this involves 8 submatrix multiplications and 4 additions. The version (Winograd’s variant [7]) of Strassen’s algorithm that we use forgoes one submatrix multiplication in exchange for eleven extra additions/subtractions, which is faster when the submatrices are large enough.

The algorithm runs as follows (visualization above):

**1.** Split \(A\) into four equally-sized quadrants \(A_{11}\), \(A_{12}\), \(A_{21}\), \(A_{22}\). The same for \(B\). (Assume first that all dimensions are even.)

**2.** Obtain the following factor matrices:

\(\displaystyle \begin{array}{ccccccc} M_{1} & = & A_{11} & \qquad & N_{1} & = & B_{11}\\ M_{2} & = & A_{12} & \qquad & N_{2} & = & B_{21}\\ M_{3} & = & A_{21}+A_{22} & \qquad & N_{3} & = & B_{12}-B_{11}\\ M_{4} & = & M_{3}-A_{11} & \qquad & N_{4} & = & B_{22}-N_{3}\\ M_{5} & = & A_{11}-A_{21} & \qquad & N_{5} & = & B_{22}-B_{12}\\ M_{6} & = & A_{12}-M_{4} & \qquad & N_{6} & = & B_{22}\\ M_{7} & = & A_{22} & \qquad & N_{7} & = & B_{21}-N_{4} \end{array}\)

**3.** Obtain \(P_{i}=M_{i}\times N_{i}\) for \(i\in\left\{ 1,2,\ldots,7\right\}\). Again depending on the dimensions, we either use Parallel IJK, or make a recursive call to Strassen’s algorithm.

**4.** The final product \(C=A\times B\) can then be obtained as follows (using some temporary matrices \(T_{i}\)):

\(\displaystyle \begin{array}{ccccccc} C_{11} & = & P_{1}+P_{2} & \qquad & C_{22} & = & T_{2}+P_{3}\\ T_{1} & = & P_{1}+P_{4} & \qquad & T_{3} & = & T_{1}+P_{3}\\ T_{2} & = & T_{1}+P_{5} & \qquad & C_{12} & = & T_{3}+P_{6}\\ C_{21} & = & T_{2}+P_{7} & \qquad \end{array}\)

### Odd Dimensions

So far this algorithm has ignored the cases when \(A\) and/or \(B\) has an odd number of rows/columns. There are several methods of dealing with this [2, 4]. For example, one could pad the matrices statically so that the dimensions are always even until the recursion passes to IJK (*static padding*); or pad only when one of the dimensions is odd (*dynamic padding*).

Alternatively one could disregard the extra rows/columns until after the algorithm completes, and then take care of them afterwards (i.e. if \(A\) has an extra row or \(B\) has an extra column, use the appropriate matrix-vector operation to calculate the remaining row/column of \(C\). If \(A\) has an extra column and \(B\) has an extra row, their product can be added on to \(C\) afterwards.) We chose this method, called *dynamic peeling*, for our implementation.

## Blocking and Tiling

Taken on its own, the above Strassen’s algorithm works well, provided both matrices are roughly square. In practice, we may encounter cases where either is highly rectangular (e.g., too tall, or long).

We solve this by slicing the matrices into blocks which are nearly square, then using Strassen’s algorithm on the submatrices. The blocking scheme is devised so that long or tall strips are avoided.

## Performance

The following charts show the performance of our hybrid Block-Strassen algorithm versus Parallel IJK on an Intel** ****®** Core i5-3337U CPU @ 1.80 GHz with 6GB RAM, running Java 1.8.0 update 40.

Tests are patterned after D’Alberto and Nicolau [1]: We ran \(C = A \times B\) for random matrices \(A\) (\(m\times n\)) and \(B\) (\(n \times p\)) , for every triple \(\left(m, n, p\right)\) in \(S^3\), where \(S = \{100,500,1000,2500,5000,7500,10000\}\). This multiplication was done three times using Parallel IJK, then three times using Hybrid Block-Strassen. The average times using each method are compared and tabulated.

Figure 3 shows the shows the multiplication time plotted against the product \(mnp\) of the dimensions. The multiplication time for IJK is \(O\left(mnp\right)\), and our empirical results show that multiplication times for both Parallel IJK and HBS are strongly linearly related to complexity. HBS, however, has a significantly smaller gradient.

The gradients of the best-fit lines suggest that as complexity approaches infinity (ignoring memory constraints), HBS will take 63.5% less time than IJK. Several data points, however, (e.g. \(m,n,p\ge5000\) ) show an even greater speedup.

Figures 4 and 5 show the time saving of HBS over Parallel IJK, in seconds (Figure 4), and as a percentage of the Parallel IJK time (Figure 5). Each table is for a specific value of \(n\) (number of columns of \(A\)), and runs over values of \(m\) (number of rows of \(A\)) and \(p\) (number of columns of \(B\)).

Finally, an accuracy test was also run to address concerns regarding the numerical stability of Strassen’s algorithm [3]. Figure 6 shows the maximum entry-wise relative error

\(\displaystyle\max_{i,j}\left|\frac{C_{i,j}^{{\rm IJK}}-C_{i,j}^{{\rm HBS}}}{C_{i,j}^{{\rm IJK}}}\right|\)

of the resulting product matrix. We see that none of the errors exceed \(2 \times 10^{-14}\) (note that we did not run Strassen’s algorithm completely to the scalar level; when the matrices \(M_i\) and \(N_i\) are too small, IJK is used. This reduces the error.), which suggests that HBS is surprisingly accurate, and a strong candidate for use in general-purpose contexts where speed is a priority.

## References

[1] Paolo D’Alberto and Alexandru Nicolau. Adaptive strassen’s matrix multiplication. In *Proceedings of the 21st Annual International Conference on Supercomputing*, ICS ’07, pages 284–292, New York, NY, USA, 2007. ACM.

[2] Hossam ElGindy and George Ferizis. On improving the memory access patterns during the execution of strassen’s matrix multiplication algorithm. In *Proceedings of the 27th Australasian Conference on Computer Science – Volume 26*, ACSC ’04, pages 109–115, Darlinghurst, Australia, Australia, 2004. Australian Computer Society, Inc.

[3] Nicholas J Higham. *Accuracy and stability of numerical algorithms*. Siam, 2002.

[4] Steven Huss-Lederman, Elaine M. Jacobson, Anna Tsao, Thomas Turnbull, and Jeremy R. Johnson. Implementation of strassen’s algorithm for matrix multiplication. In *Proceedings of the 1996 ACM/IEEE Conference on Supercomputing*, Supercomputing ’96, Washington, DC, USA, 1996. IEEE Computer Society.

[5] Steven S. Skiena. *The Algorithm Design Manual*. Springer Publishing Company, Incorporated, 2nd edition, 2008.

[6] Volker Strassen. Gaussian elimination is not optimal. *Numerische Mathematik*, 13(4):354–356, 1969.

[7] Shmuel Winograd. On multiplication of 2×2 matrices. *Linear algebra and its applications*, 4(4):381– 388, 1971.

## 197 Comments

Fastest Java Matrix Multiplication | Certified Quantitative Analyst

hezvntwb http://www.gh4zl96o642q04t0rrki907980fwms2vs.org/

ahezvntwb

[url=http://www.gh4zl96o642q04t0rrki907980fwms2vs.org/]uhezvntwb[/url]

Assured Hand Sanitizer 2 Oz

Distillation Plant

Gastrostomy Tube supplier

Cnc Grinding Services

Home Evaporative Cooler

Bosch Control Valve

Toyota

Granular Activated Carbon Price

TgSBIHhoC

Buy Lapel Pins

Strong Pvc Bond Super Glue

China Canvas Interlining for Tailoring and Hair Canvas Interlining price，China Seamless Knitting Machine，China Sports Suit Knitting Machine Supplier

100% Cotton Fabric

Aluminum Brake Line

China Outer Workwear and out Door Garment price

Metal Core Circuit Board

Best Heavyweight T Shirts Factories

Composting Rotating Mixer Machine

Rmu Lbs

Best Quality Melon Seeds

Faux Fur Zip Up Jacket

Magnetic Lid Gift Box

Ftth Fiber Optic Distribution Box

BXL

赌厅网投

53242-76-5

Biosafety Cabinet For Sale

Polo Shirts For Men

Outdoor Sofa Set

Expeller Seal Pump

Mining Cyclone

Car Wheel Rim Covers

carton folding machine

Cas:16648-44-5

China Diamond Mesh Fence

Carbon Fiber Composite

Does Anodized Aluminum Wear Off

Custom Quartz

12 V Air Conditioner Truck

g105 Api 5dp Drill Pipe

Craft Cardstock

スーパーコピーブランド評価

Tablet Pill Making Equipment

Gucciグッチサングラススーパーコピー

Drip Irrigation Tape Fittings

LouisVuittonルイヴィトンバッグスーパーコピー

Cedar Wood Shingles

Roasted Soya Seeds

LouisVuittonルイヴィトン靴スーパーコピー

Chain Ratchet Puller

Gucciグッチバッグスーパーコピー

Finger Brace

ブランドブレスレットスーパーコピー

Black Quartz Kitchen Countertops

Diorディオールサングラスコピー

ブランドバッグコピー

Joint Coupling

ブランドHermesエルメスブレスレットコピー代引き

Bulk Sports Bras

Bfm1011 Diesel Oil Pump

Chanelシャネルブレスレットコピー

ブランドコピー専門店

Led Umbrella

Electric Tricycles Wholesalers

ブランドバッグコピー

ブランド時計コピー

Acrylic Led Light Guide Plate

Beer Brewing Tanks

コピー時計

ブランドコピー代引き

Bmu With Goose-Neck Boom

ブランド時計コピー

Cargo Hold Inspection Survey

xcmg spare parts

スーパーコピーバッグ

ブランドCartierカルティエ指輪コピーN級品

Pc Cut Length& Threaded Wire

Chanelシャネルベルトスーパーコピー

PCB Plate Making

Gucciグッチ靴スーパーコピー

Axial Bifurcated Fan

Cleated Incline Conveyor

Gucciグッチサングラスコピー

日本国内発送通販ブランドコピー安全後払い専門店

Deck Roll Forming Machine

Omegaオメガブランドコピー代引き

Metal Detector Checkweigher

Hermesエルメスブレスレット販売店

Ion Exchange Resin Chemical Formula

Delta Airlines Phone Number | Delta airlines customer service phone number https://telegra.ph/Delta-Airlines-Manage-Booking–18556702491-10-01

Celineセリーヌブランドコピー代引き

modern squat toilet

Medrad Envision Ct

LouisVuittonルイヴィトンベルト販売店

Long Sleeve Sun Shirt Supplier

Hermesエルメスベルトコピー

ブランドChanelシャネルバッグコピー代引き

Main Engine Exhaust Valve Supplier

Steel Flange

ブランドPradaプラダバッグコピーN級品

control of pest San Diego service https://www.webdesignerdepot.com/?s=control+of+pest+%E2%98%8E+1%28844%299484793+San Diego+service+phone+number

sqJyugVWKnEU

ブランド財布コピー

Inverter Cutting Machine Price

ブランド財布コピー

Movable Side Table

Delta Air lines Louisiana booking flight service https://search.yahoo.com/tablet/s?p=Delta+airlines+1+855-670-2491+book+a+flight&ei=UTF-8&age=1m&fr2=time&btf=m

Delta Air lines MS booking flight service https://search.yahoo.com/tablet/s?p=Delta+airlines+1+855-670-2491+book+a+flight&ei=UTF-8&age=1m&fr2=time&btf=m

75 Alcohol Wipes Disinfectant

ブランドTiffanyティファニー指輪コピー代引き

ブランドコピー専門店

Electrostatic Disinfectant

ブランド財布コピー

Pa6 Gf

Ply Shuttering Concrete

ブランドバッグコピー

Nano zinc oxide for catalyst

Carbon Steel Zinc Plated Sleeve Anchor with Conical Nut and C Hook

ブランドバッグコピー

Electric Humidifier

Иван Грозный – смотреть онлайн в хорошем качестве https://bit.ly/ivan_groznii

Paracord Leather Dog Collar

コピー時計

10 French Catheter

8HP Water-cooled Box Chiller

ブランド財布コピー

Eyebrow Tattoo Removal

Others

TIMING OIL VALVE Solenoid K5T45591

ブランドバッグコピー

Copper Tube Boiler

Diesel Fuel Pump

スーパーコピーブランド

Car Gps

2 Pin High Speed Input Output Connector Plug

スーパーコピーバッグ

F6906Z Bearing

スーパーコピーバッグ

2mp 25x Digital Zoom Camera Module

コピー時計

Moule 脿 injection assist茅e par gaz

FOR HINO

FsZMgHlyqt

617-85-6

Gasunterstützte Spritzgussform

ブランドコピー代引き

Console, what has changed in definitely takes the cake. Kellyann Tony Janicki

スーパーコピーブランド

transitional polishing pad

7 Pin Automotive Electrical Wire Connector Plug

60 Inch Bathroom Vanity

Head Gasket For TOYOTA 3E

ブランドバッグコピー

custom die casting aluminum alloy

スーパーコピーブランド

Soft Plyo Box

Metal Bond Cutting Disc

ブランドバッグコピー

Double Rocker Switch

Heat Resistant VDE H05SJ-K Fibre Braided Rubber Single Core Cable

Venturi Sludge Pump

ブランドコピー代引き

48654-0K010

コピー時計

Barber Shop Mirrors With Led Lights

Kogellagercomponenten:

Newest Zinc oxide for paint coating

スーパーコピーブランド

Flens zeefklep

Indirect ZnO powder Price List

ブランド時計コピー

China Polyphylene Powder Coating for Pipeline Anticorrosion Factory

ブランドバッグコピー

Centrifuge Tube 100ml

That could be the finish of this write-up. Right here you will come across some web sites that we consider youll value, just click the hyperlinks. Liz Dudley Carlo

As I website possessor I think the written content here is rattling wonderful, regards for your efforts. Marna Ad Grous

Body Tattoo Removal Beauty Machine

Cheap Floating Gold Plain Suction Bucket Dredger

スーパーコピーバッグ

Electric Trail Bike

Advanced HPMC for Mortar Additive

スーパーコピーブランド

Durable Acid Black 210

ブランドコピー専門店

Knee Support Tape

China Polyester Powder Coating Factory

Supply chain service for metal

スーパーコピーブランド

ブランドコピー代引き

Sulphur Black BR Free Sample

Sublimation Paper For Ink Jet Printer

ブランドコピー専門店

Latest Selling Pure Zinc Oxide Powder Feed Grade

Carbide Saw Blade Factory

Polyethylene Foam Board

ブランドコピー専門店

Construction grade HPMC Brands

ブランド時計コピー

Precision Telecom Machining Parts Suppliers

Inicio Máquina para esculpir el cuerpo

Newest Zinc Oxide Glass Grade

スーパーコピーバッグ

S235JO I-beam

Wholesale Indoor Powder Coating Powder

ブランドバッグコピー

Tws Mini Earbuds

ブランドコピー専門店

Hypromellose In Stock

cardboard box custom logo

ブランドコピー専門店

Cosmetic Grade Zinc Oxide Powder Non Nano Price List

Dog Water Bottle Dispenser

New 14 Inch Lake Dredging Equipment For Rock Dredge Price List

ブランド時計コピー

raised bed planter

Bamboo Stain Color Quotes

Classy Sulfanilic Acid For Optical Brightener

China Metal Mailbox Post

Outdoor Powder Coating Price

China High Temperature Powder Coating Powder suppliers

Multi Cat Litter

China Wholesale Eye Shadow Eyeshadow Palette Suppliers

Fashion High Precision Aluminum Aircraft Machining Parts

Buy Floating Gold Plain Suction Bucket Dredger

China Medical Gas Manifold

Reactive red 3BS Manufacturers

Uhmwpe Fiber For Slings

Volumetric thin oil distributor

Newest Plastic Pet Blowing Bottles Blow Mold

PTFE Gasket Sheet with Silica filler

Full Support Sports Bra

Easy-maintainable Zinc Oxide Rubber Grade

Magnetic Nail Tool

Scalp Vein Set

CNC Machining Milling Telecom Parts Quotation

8 Chicken Coop

12 Inch Cutter Suction Dredger China

Máquina de control de seguridad de rayos X

Quality Impurity free zinc oxide

Advanced Fully Hydraulic Cutter Head 24 Suction Cutter Dredger Barge

Gu10 Led Light Fittings

Baby Infant Toothbrush

Classy High Precision CNC Milling Machining Parts

Low Price Coating Grade Zinc Oxide Powder

Rapid Test Positive

Body Sculpt Manchine

Easy-maintainable Cosmetic Zinc Oxide Powder

HU66 Inner Groove Lock Pick

HPMC for Mortar Price

CAS NO.:129-09-9 Made in China

Brake Shoe Lining

Weight Terminal Manufacturer

Cheap 8 Inch Horizontal Sand Pump For Dredger And River Sand

Electronic Grade Zinc Oxide 99.7% In Stock

Anti Mouse Repeller

Promotional Hoodies Quotation

China Oxymeter Pulse Oximeter

metal practical products accept logo customization Promotion pen metal practical products accept logo customization Promotion pen

High Mast Led Flood Light

Buy Discount BU-50-114 Bypass Oil Filter

Razor Packing Machine

China SmallOrders G0114 wedding valentine small business gifts set suppliers

Best Cell Repeater

SmallOrders G020127 Gypsophila dry flower gift Rose bear box Brands

Check Valve Butterfly Type

Latest Selling SmallOrders G021204 Photo greeting card

Ceramic Oxygen Diffuser

Discount Auto Parts CNC Precision Machining

40mm Blower Fan

Glass Lighting

Rustic Oak Multilayer Engineered Wood Flooring

Convex Truck Mirrors

SmallOrders G020303 Creative Crystal Trophy

Promotional accept custom portable promotional power bank with four wire large capacity SmallOrders G070102 Promotional items Price

Braided Nylon Line

Classy SmallOrders G020108 Halloween decorations

Asic S17

CO2 Laser Marking Machine for Leather Carvings and Cutting

Gellan Gum Price

Fine Quality Fiberglass Insect Screen

Red Disposable Head Cover Surgical Bouffant Cap Polypropylene

Bamboo Faucet

Top Computerized Medical Control Volumetric Infusion Pump (THR-IP100 I)

Commercial Serve Ice Cream Machine 2+Mixed Flavor Ice Cream Machine Snack Machinery Soft Ice Cream Maker

Ironworker Boots

Tesmart Kvm Switch

Dn10 Stainless Steel SS316L Aspetic Diaphragm Valves

Multi Usb Dock

Auto steel Bar Bender Bending Machine

China Laser Cutting Machine For Tubes manufacturers

Examination Table

BXL

Carbon Fiber Laser Cutting Machine Made in China

15 Ga Galvanized Nails

High Power Fiber Laser Cutter Factory

677304-83-5

Design New Brown Cherry Wood Veneer Modern Kitchen Cabinets

Car Seat Protector For Baby Seat

Fiber Laser Cutting Machine For Metal Brands

Fully Enclosed Laser Cutting Machine Free Sample

Real Fox Fur Women Gilet

Wld8400 Ce DIY Paint Spray Booth China Factory for Sale

Earrings Silver

China Handheld Laser Welder manufacturers

Table Mould

Full Automatic Canned Sliced Peach Production Machinery

Clear Pvb For Car Glass

Kids House Bed

Driving Worklamp Spot Flood Round 9inch LED Work Light

Basement Floor Underlayment

Plastic Cap / color umbrella head Ring shank /screw Shank Roofing Nails with washer for Construction

1000 Floor Deck Roll Forming Machine for Myanmar Customer

8 Mil Nitrile Gloves

Volvo Excavators Bucket Spare Parts Bucket Tooth Pins for Ec480

Embossed Acrylic Sheets

Yellow Road Construction Warning Light

Araceae

Quality High Power Fiber Laser Machine

H Link For Sk200-3 Excavator

PVC Tarpaulin Fabric for Truck Cover

High Quality Battery

China New Enclosed Toe Child Girls Summer School Beach Sandals

375w Mono Solar Panel

Careplus Vinyl Gloves

Fiber Optic Sc/LC/Sm Fiber Connector

Animal Nutrition Ingredient

Non-Toxic, Odorless 10 PCS Textured Colorful EVA Ordinary Towel Foam Sheets for DIY Crafts

3 Flute End Mill

8000w 72v Electric Bike Fastest Electric Bicycle

type D shackle

Rfid Library Label

bolt type anode

Cashew Nut Packing Machine

marine bulwark ladder

Copper Coffee Machine

Symmetrical Type El Combined Windlass Mooring Winch

Antique Blue Glass Perfume Bottle

Sneaker Sport Shoes

Even Cable Can Be Used As The Old Line Change New Line

Skid Plates

Rolling-Wheel Unloading Buckle

Joining shackle

Aluminum Component er Metal Plastic Precision Steel Shaft Pin Guide Rail Anodized Custom Box Knob Product Cnc Machined Part

After looking at a number of the blog articles on your site, I honestly appreciate your way of writing a blog. I book-marked it to my bookmark site list and will be checking back soon. Please visit my web site as well and let me know what you think.|

Laser Cnc Engraver

LED A65 Light Bulb

A60 Quick Action Weathertight Steel Door

Blank Cutting Board

Marine Stainless Steel Fixed Circle Window

Aseptic Liquid Nitrogen Dosing Machine

Marine Draft Ladder

Gas Sensor Price

binding chains

Surface Sanding Machine

Aluminum Square Tubing Supplier

flayt rope block

Page A Day Tear Off Calendar Printing

Kitchen Supplies

Cheap Defoamer Sewage Manufacturer

CB436 cleat fairlead type A

Manual Lever Wire Rope Block

Snowmobile Tracks Cheap OEM

China Defoamer Manufacturer China Pricelist

Marine Cranes

Mini Digger Rubber Tracks to Norwegians

Multi Type Shoulder Strap Messenger Bag

Horizontal Lead Sheave

Wholesale Embossed Polycarbonate

EMI Shielding Door

Best Antifoam Sewage Factories

Clases De Foam

Aluminum Rectangular Sunk Watertight Hatch Cover