A Matrix for the New HPL-AI Benchmark - Cleve Moler on Mathematics and Computing
 

My colleagues are looking for a matrix to be used in a new benchmark. They've come to the right place.

[B]Contents[/B]

[LIST][*][URL="https://www.labfans.com/bbs/#6f5315d6-ad46-4b35-8764-677b167da963"]Email[/URL][*][URL="https://www.labfans.com/bbs/#ec0c12b2-744f-4a38-950a-cc5be7fd721c"]Symmetric Hilbert Matrix[/URL][*][URL="https://www.labfans.com/bbs/#c4ed2873-690a-44c2-9287-ef44ffcc9484"]Nonsymmetric Hilbert Matrix[/URL][*][URL="https://www.labfans.com/bbs/#5aeb53c5-275a-4d87-bb57-1cd00c4a7bdd"]Benchmark Matrix[/URL][*][URL="https://www.labfans.com/bbs/#d3942f58-edb5-48f0-891c-7a7ecec1af6b"]Example[/URL][*][URL="https://www.labfans.com/bbs/#58364797-0112-4455-89cb-4d4e759bbd52"]Animation[/URL][*][URL="https://www.labfans.com/bbs/#781fa356-fe10-46fb-b54d-8924359bdada"]Gaussian elimination[/URL][*][URL="https://www.labfans.com/bbs/#532aaf80-f812-47ae-9a20-0b12d101aacb"]Condition[/URL][*][URL="https://www.labfans.com/bbs/#0245bd74-6fc1-470b-b562-907250503a72"]sigma_1[/URL][*][URL="https://www.labfans.com/bbs/#574d19eb-ad2d-4ebd-b451-8141696e0431"]sigma_n[/URL][*][URL="https://www.labfans.com/bbs/#8e373526-14f7-4cf3-b08e-807cc5106d2f"]sigma_1/sigma_n[/URL][*][URL="https://www.labfans.com/bbs/#d064d4d3-26d6-4255-b4d3-e4f6669b328b"]Overflow[/URL][*][URL="https://www.labfans.com/bbs/#a031341e-49db-4d70-ba25-4115efd35419"]Thanks[/URL][/LIST]
[B]Email[/B]

A couple of weeks ago I got this email from Jack Dongarra at the University of Tennessee.

For this new HPL-AI benchmark, I'm looking for a matrix that is not symmetric, is easily generated (roughly O(n^2) ops to generate), is dense, doesn’t require pivoting to control growth, and has a smallish condition number ( -1, the largest element is on the diagonal and lu(A(n,mu)) does no pivoting.

format short mu = -1 [L,U] = lu(A(n,mu)) mu = 1 [L,U] = lu(A(n,mu)) mu = -1 L = 1.0000 0 0 0 0 0.2083 1.0000 0 0 0 0.2778 0.1748 1.0000 0 0 0.4167 0.2265 0.1403 1.0000 0 0.8333 0.3099 0.1512 0.0839 1.0000 U = 1.2000 0.1667 0.1429 0.1250 0.1111 0 1.1653 0.1369 0.1168 0.1019 0 0 1.1364 0.1115 0.0942 0 0 0 1.1058 0.0841 0 0 0 0 1.0545 mu = 1 L = 1.0000 0 0 0 0 0.1094 1.0000 0 0 0 0.0972 0.0800 1.0000 0 0 0.0875 0.0729 0.0626 1.0000 0 0.0795 0.0669 0.0580 0.0513 1.0000 U = 1.1429 0.1250 0.1111 0.1000 0.0909 0 1.0974 0.0878 0.0800 0.0734 0 0 1.0731 0.0672 0.0622 0 0 0 1.0581 0.0542 0 0 0 0 1.0481 [B]Condition[/B]

Let's see how the 2-condition number, $\sigma_1/\sigma_n$, varies as the parameters vary. Computing the singular values for all the matrices in the following plots takes a little over 10 minutes on my laptop.

[B]sigma_1[/B]

load HPLAI.mat s1 sn n mu surf(mu,n,s1) view(25,12) xlabel('mu') ylabel('n') set(gca,'xlim',[-0.9 1.0], ... 'xtick',[-0.9 -0.5 0 0.5 1.0], ... 'ylim',[0 2500]) title('\sigma_1') [IMG]http://blogs.mathworks.com/cleve/files/HPLAI_blog_01.png[/IMG] The colors vary as mu varies from -0.9 up to 1.0. I am staying away from mu = -1.0 where the matrix looses diagonal dominance. The other horizontal axis is the matrix order n. I have limited n to 2500 in these experiments.

The point to be made is that if mu > -0.9, then the largest singular value is bounded, in fact sigma_1 < 2.3.

[B]sigma_n[/B]

surf(mu,n,sn) view(25,12) xlabel('mu') ylabel('n') set(gca,'xlim',[-0.9 1.0], ... 'xtick',[-0.9 -0.5 0 0.5 1.0], ... 'ylim',[0 2500]) title('\sigma_n') [IMG]http://blogs.mathworks.com/cleve/files/HPLAI_blog_02.png[/IMG] If mu > -0.9, then the smallest singular value is bounded away from zero, in fact sigma_n > .75.

[B]sigma_1/sigma_n[/B]

surf(mu,n,s1./sn) view(25,12) xlabel('mu') ylabel('n') set(gca,'xlim',[-0.9 1.0], ... 'xtick',[-0.9 -0.5 0 0.5 1.0], ... 'ylim',[0 2500]) title('\sigma_1/\sigma_n') [IMG]http://blogs.mathworks.com/cleve/files/HPLAI_blog_03.png[/IMG] If mu > -0.9, then the condition number in the 2-norm is bounded, sigma_1/sigma_n < 2.3/.75 $\approx$ 3.0 .

[B]Overflow[/B]

The HPL-AI benchmark would begin by computing the LU decomposition of this matrix using 16-bit [URL="https://blogs.mathworks.com/cleve/2019/02/18/experiments-with-variable-format-half-precision/"]half-precision floating point arithmetic[/URL], FP16. So, there is a signigant problem if the matrix order n is larger than 65504. This value is realmax, the largest number that can be represented in FP16. Any larger value of n overflows to Inf.

Some kind of scaling is going to have to be done for n > 65504. Right now, I don't see what this might be.

The alternative half-precision format to FP16 is Bfloat16, which has three more bits in the exponent to give realmax = 3.39e38. There should be no overflow problems while generating this matrix with Bfloat16.

[B]Thanks[/B]

Thanks to Piotr Luszczek for working with me on this. We have more work to do.

[RIGHT][COLOR=gray][I]
[URL="javascript:grabCode_090b2b07d699444096989550bd6fcef7()"][I]Get the MATLAB code (requires JavaScript)[/I][/URL]

Published with MATLAB&reg; R2019b
[/I][/COLOR][/RIGHT]