July 2017 - mathfun@mailman.xmission.com

Re: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ?
by Henry Baker 03 Jul '17

03 Jul '17

If you have high speed raster graphics hardware, you may already have the capability for 2D transpose. There's also the famous (at least in computer graphics circles) "three shears" algorithm for image rotation by 90 degrees without any loss of information: 1. Shear the image 45 degrees to the right. 2. Shear the image 90 degrees down. 3. Shear the image 45 degrees to the left. The problem is that step #2 is usually just as hard in most memory systems as transposition, unless the hardware is set up to pick up word slices -- e.g., give me the 13th bit each of 32 words arranged as a 32-bit word. At 01:10 PM 7/2/2017, rcs(a)xmission.com wrote: >Transposition can be done in log2(N) passes over the matrix. >Imagine cutting your matrix into quarters, and exchanging the upper right >quarter with the lower left quarter. Next, do the same thing within each >quarter. Etc. If N isn't a power of 2, you may have to round it up; unsure. > >Rich > >----- >Quoting Henry Baker <hbaker1(a)pipeline.com>: >>Thanks, Adam. >> >>I'm already doing some of what you suggest. >> >>Is there any cleverness for *transposing* such bit matrices ? >> >>(As an aside, do *least squares* have any relevance over GF(2)?) >> >>Note that Gaussian elimination on extremely long vectors (much >>longer than the rank of the system) is faster if you invert the >>small square (rank x rank) matrix by itself, and then propagate that >> info to the rest of each row. >> >>Is there any cleverness that might be achieved if one had access to >>a *polynomial* multiply (and/or divide) operation over GF(2)[x] ? I >> seem to recall that this sort of HW is finally starting to show up >>as a "carryless multiply" operation. >> >>At 11:06 AM 7/2/2017, Adam P. Goucher wrote: >>>Yes, if the matrix has <= 64 rows, then you can store the columns as >>>64-bit integers and perform column operations using bitwise XOR. Also, >>>you can determine the uppermost and lowermost non-zero elements in a >>>column using the __builtin_clzll() instruction and variants thereof. >>> >>>This generalises, of course; with N rows, you can store each column >>>as a vector of ceil(N/64) 64-bit integers and perform column operations >>>with as many instructions. With SIMD, you can actually get away with as >>>few as ceil(N/256) instructions per column operation. >>> >>>The fact that there's only one non-zero element of GF(2) is also >>>helpful since there's no need to multiply the columns -- add/subtract >>>(i.e. XOR) is the only operation you ever need to perform! >>> >>>I'm using exactly this procedure in my PhD research on topological data >>>analysis. In particular, computing the persistent homology barcode from >>>the boundary map is (a slightly modified version of) Gaussian elimination >>>over GF(2). >>> >>>Best wishes, >>> >>>Adam P. Goucher >>> >>>>Sent: Sunday, July 02, 2017 at 6:29 PM >>>>From: "Henry Baker" <hbaker1(a)pipeline.com> >>>>To: math-fun(a)mailman.xmission.com >>>>Subject: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ? >>>> >>>>Other than Strassen? >>>> >>>>I.e., are there any bit-twiddling hacks that are particular to >>>>GF(2) for Gaussian elimination?

2 1

[math-fun] Exploding the myths of Ada Lovelace's mathematics
by Henry Baker 03 Jul '17

03 Jul '17

FYI -- None of the links below are behind paywalls. https://www.maths.ox.ac.uk/node/25695 Exploding the myths of Ada Lovelace's mathematics Ada Lovelace (1815â1852) is celebrated as "the first programmer" for her remarkable 1843 paper which explained Charles Babbage's designs for a mechanical computer. New research reinforces the view that she was a gifted, perceptive and knowledgeable mathematician. Christopher Hollings and Ursula Martin of Oxford Mathematics, and Adrian Rice, of Randolph-Macon College in Virginia, are the first historians of mathematics to investigate the extensive archives of the Lovelace-Byron family, held in Oxford's Bodleian Library. In two recent papers in the Journal of the British Society for the History of Mathematics and in Historia Mathematica they study Lovelace's childhood education, where her passion for mathematics was complemented by an interest in machinery and wide scientific reading; and her remarkable two-year "correspondence course" on calculus with the eminent mathematician Augustus De Morgan, who introduced her to cutting edge research on the nature of algebra. The work challenges widespread claims that Lovelace's mathematical abilities were more "poetical" than practical, or indeed that her knowledge was so limited that Babbage himself was likely to have been the author of the paper that bears her name. The authors pinpoint Lovelace's keen eye for detail, fascination with big questions, and flair for deep insights, which enabled her to challenge some deep assumptions in her teacher's work. They suggest that her ambition, in time, to do significant mathematical research was entirely credible, though sadly curtailed by her ill-health and early death. The papers, and the correspondence with De Morgan, can be read in full on the website of the Clay Mathematics Institute, who supported the work, as did the UK Engineering and Physical Sciences Research Council. http://www.sciencedirect.com/science/article/pii/S0315086017300319 The LovelaceâDe Morgan mathematical correspondence: A critical re-appraisal Christopher Hollings, Ursula Martin, Adrian Rice Available online 9 May 2017 Abstract Ada Lovelace is widely regarded as an early pioneer of computer science, due to an 1843 paper about Charles Babbage's Analytical Engine, which, had it been built, would have been a general-purpose computer. However, there has been considerable disagreement among scholars as to her mathematical proficiency. This paper presents the first account by historians of mathematics of the correspondence between Lovelace and the mathematician Augustus De Morgan from 1840â41. Detailed contextual analysis allows us to present a corrected ordering of the archive material, countering previous claims of Lovelace's mathematical inadequacies, and presenting a more nuanced assessment of her abilities. http://www.tandfonline.com/doi/pdf/10.1080/17498430.2017.1325297 The early mathematical education of Ada Lovelace Christopher Hollings, Ursula Martin & Adrian Rice To cite this article: Christopher Hollings, Ursula Martin & Adrian Rice (2017): The early mathematical education of Ada Lovelace, BSHM Bulletin: Journal of the British Society for the History of Mathematics, DOI: 10.1080/17498430.2017.1325297 CHRISTOPHER HOLLINGS and URSULA MARTIN University of Oxford, UK ADRIAN RICE Randolph-Macon College, USA Ada, Countess of Lovelace, is remembered for a paper published in 1843, which translated and considerably extended an article about the unbuilt Analytical Engine, a general-purpose computer designed by the mathematician and inventor Charles Babbage. Her substantial appendices, nearly twice the length of the original work, contain an account of the principles of the machine, along with a table often described as 'the first computer program'. In this paper we look at Lovelace's education before 1840, which encompassed older traditions of practical geometry; newer textbooks influenced by continental approaches; wide reading; and a fascination with machinery. We also challenge judgements by Dorothy Stein and by Doron Swade of Lovelace's mathematical knowledge and skills before 1840, which have impacted later scholarly and popular discourse.

1 0

Re: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ?
by Henry Baker 03 Jul '17

03 Jul '17

The 3 shears procedure is more exactly: 1. Shear the bitmap horizontally 45 degrees to the right; the X-axis stays the same, the Y-axis tilts 45 degrees to the right. 2. Shear the bitmap vertically 45 degrees down; the Y-axis drops down 45 degrees to horizontal, the X-axis drops down 45 degrees below horizontal. 3. Shear the bitmap horizontally 45 degrees to the left; the Y-axis remains horizontal, the X-axis shifts 45 degrees to become vertical. At 01:51 PM 7/2/2017, Henry Baker wrote: >If you have high speed raster graphics hardware, you may already have the capability for 2D transpose. > >There's also the famous (at least in computer graphics circles) "three shears" algorithm for image rotation by 90 degrees without any loss of information: > >1. Shear the image 45 degrees to the right. >2. Shear the image 90 degrees down. >3. Shear the image 45 degrees to the left. > >The problem is that step #2 is usually just as hard in most memory systems as transposition, unless the hardware is set up to pick up word slices -- e.g., give me the 13th bit each of 32 words arranged as a 32-bit word. > >At 01:10 PM 7/2/2017, rcs(a)xmission.com wrote: >>Transposition can be done in log2(N) passes over the matrix. >>Imagine cutting your matrix into quarters, and exchanging the upper right >>quarter with the lower left quarter. Next, do the same thing within each >>quarter. Etc. If N isn't a power of 2, you may have to round it up; unsure. >> >>Rich >> >>----- >>Quoting Henry Baker <hbaker1(a)pipeline.com>: >>>Thanks, Adam. >>> >>>I'm already doing some of what you suggest. >>> >>>Is there any cleverness for *transposing* such bit matrices ? >>> >>>(As an aside, do *least squares* have any relevance over GF(2)?) >>> >>>Note that Gaussian elimination on extremely long vectors (much >>>longer than the rank of the system) is faster if you invert the >>>small square (rank x rank) matrix by itself, and then propagate that >>> info to the rest of each row. >>> >>>Is there any cleverness that might be achieved if one had access to >>>a *polynomial* multiply (and/or divide) operation over GF(2)[x] ? I >>> seem to recall that this sort of HW is finally starting to show up >>>as a "carryless multiply" operation. >>> >>>At 11:06 AM 7/2/2017, Adam P. Goucher wrote: >>>>Yes, if the matrix has <= 64 rows, then you can store the columns as >>>>64-bit integers and perform column operations using bitwise XOR. Also, >>>>you can determine the uppermost and lowermost non-zero elements in a >>>>column using the __builtin_clzll() instruction and variants thereof. >>>> >>>>This generalises, of course; with N rows, you can store each column >>>>as a vector of ceil(N/64) 64-bit integers and perform column operations >>>>with as many instructions. With SIMD, you can actually get away with as >>>>few as ceil(N/256) instructions per column operation. >>>> >>>>The fact that there's only one non-zero element of GF(2) is also >>>>helpful since there's no need to multiply the columns -- add/subtract >>>>(i.e. XOR) is the only operation you ever need to perform! >>>> >>>>I'm using exactly this procedure in my PhD research on topological data >>>>analysis. In particular, computing the persistent homology barcode from >>>>the boundary map is (a slightly modified version of) Gaussian elimination >>>>over GF(2). >>>> >>>>Best wishes, >>>> >>>>Adam P. Goucher >>>> >>>>>Sent: Sunday, July 02, 2017 at 6:29 PM >>>>>From: "Henry Baker" <hbaker1(a)pipeline.com> >>>>>To: math-fun(a)mailman.xmission.com >>>>>Subject: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ? >>>>> >>>>>Other than Strassen? >>>>> >>>>>I.e., are there any bit-twiddling hacks that are particular to >>>>>GF(2) for Gaussian elimination?

1 0

Re: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ?
by Henry Baker 02 Jul '17

02 Jul '17

Thanks, Adam. I'm already doing some of what you suggest. Is there any cleverness for *transposing* such bit matrices ? (As an aside, do *least squares* have any relevance over GF(2)?) Note that Gaussian elimination on extremely long vectors (much longer than the rank of the system) is faster if you invert the small square (rank x rank) matrix by itself, and then propagate that info to the rest of each row. Is there any cleverness that might be achieved if one had access to a *polynomial* multiply (and/or divide) operation over GF(2)[x] ? I seem to recall that this sort of HW is finally starting to show up as a "carryless multiply" operation. At 11:06 AM 7/2/2017, Adam P. Goucher wrote: >Yes, if the matrix has <= 64 rows, then you can store the columns as >64-bit integers and perform column operations using bitwise XOR. Also, >you can determine the uppermost and lowermost non-zero elements in a >column using the __builtin_clzll() instruction and variants thereof. > >This generalises, of course; with N rows, you can store each column >as a vector of ceil(N/64) 64-bit integers and perform column operations >with as many instructions. With SIMD, you can actually get away with as >few as ceil(N/256) instructions per column operation. > >The fact that there's only one non-zero element of GF(2) is also >helpful since there's no need to multiply the columns -- add/subtract >(i.e. XOR) is the only operation you ever need to perform! > >I'm using exactly this procedure in my PhD research on topological data >analysis. In particular, computing the persistent homology barcode from >the boundary map is (a slightly modified version of) Gaussian elimination >over GF(2). > >Best wishes, > >Adam P. Goucher > >> Sent: Sunday, July 02, 2017 at 6:29 PM >> From: "Henry Baker" <hbaker1(a)pipeline.com> >> To: math-fun(a)mailman.xmission.com >> Subject: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ? >> >> Other than Strassen? >> >> I.e., are there any bit-twiddling hacks that are particular to GF(2) for Gaussian elimination?

1 0

[math-fun] Any cool hacks for Gaussian elimination over GF(2) ?
by Henry Baker 02 Jul '17

02 Jul '17

Other than Strassen? I.e., are there any bit-twiddling hacks that are particular to GF(2) for Gaussian elimination?

2 1

Re: [math-fun] Equal sums of powers
by Dan Asimov 02 Jul '17

02 Jul '17

<< Prouhet's Thue-Morse based solution turns out to be ... Solution to what? —Dan

2 1

[math-fun] Unfolding questions
by David Wilson 01 Jul '17

01 Jul '17

1. For a given polyhedron, what is the minimal number edges that need to be cut to unfold it into a connected planar surface? For example, 3 edges are necessary for a tetrahedron, I think 7 for a cube. 2. Is this minimal number a function of the number of faces, edges and vertices of the polyhedron? 3. Is this minimal number unique? Does any unfolding of the same polyhedron have the same number of edge cuts? 4. If (3) is false, is there a polyhedron where some unfolding has more edge cuts, but shorter total edge cut length, than some other unfolding? 5. Is there a convex polyhedron for which some unfolding exhibits overlapping faces in the plane? If so, what is the smallest number of faces on such a polyhedron?

9 19