Mathematics desk
< October 6	<< Sep \| October \| Nov >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 7

Storage of matrices containing all standard basis columns

The following type of matrix occurs frequently in linear programming, specifically the simplex method. Specifically, M is a tableau if it's a column permutation of a matrix of the form [I|A] where I is the identity matrix and A is arbitrary. It seems highly inefficient to store the entire matrix as an array when just A and a permutation have all the necessary information. Right now I'm dealing with nx(n+24) matrices where n is over a thousand. So I'm thinking that only storing the nx24 matrix that's actually needed would reduce the size by a factor of 40 and speed up operations on the matrices by a similar amount. I've started rolling my own Python code to perform operations on tableaux stored as A + permutation rather than the full matrix, but I was a bit surprised that this scheme isn't mentioned in the article on sparse matrices. We do have an article on the revised simplex method, which stores the inverse of a subset of the columns of M rather than M itself, but it seems to me that would be most useful when the number of columns is much larger than the number of rows, rather than only slightly larger which is what I'm dealing with. I've also heard of schemes where you only store the original matrix and a sequence of pivot matrices, but again, that doesn't sound like it would be useful here because in general the number of pivot operation is much more than 24. On the other hand, I have a hard time believing this storage method hasn't already been used in the past and isn't already part of some numerical library somewhere. I don't mind "reinventing the wheel" if it helps to understand what's going on with a given algorithm, but it would be nice to know if the "the wheel" has indeed already been invented or not. --RDBury (talk) 14:02, 7 October 2021 (UTC)[reply]

I thought in the simplex method, you have to a series of pivots similar to matrix inversion, with starts with a similar-looking augmented matrix. Is storage really a problem for matrices of the size you're describing, with today's computers? SciPy has some linear programming tools included and you may be better off using those. There is apparently a front end called PuLP that makes things easier. I hadn't heard of it before doing a web search just now. Surprisingly, pandas doesn't seem to have linear programming. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 09:04, 8 October 2021 (UTC)[reply]

There is also the speed-up by a factor of almost 40. A Google scholar search on "storage"+simplex+pivot+tableau finds several publications that claim an implementation reducing computer storage. --Lambiam 12:16, 8 October 2021 (UTC)[reply]

Yes, running out storage itself is not the practical consequence, since even my old computer can safely store 8 megs of data in RAM (and stream a video at the same time), but storage seems to be a cause of a performance bottleneck. Every operation has to read through the whole array, and this seems wasteful when the 95% of the computations are 0*0-0*0=0. Of course there's always a trade-off; a simple storage method such as putting everything in a large array is easier to program and less prone to errors, and the more complicated code needed for more efficient storage may in itself cause a slowdown. Of course performance is only an issue if the computer takes more time to finish a computation than it takes for you to wonder about what the result will be. But I've reached the point where the additional programming seems like it may be worth it. Anyway, I'll look through the Google results to see if there's anything relevant. --RDBury (talk) 10:38, 9 October 2021 (UTC)[reply]

SI Prefixes

Is this a reliable source?

https://sites.google.com/view/infinitesimal-prefixes/home — Preceding unsigned comment added by Trakaplex (talk • contribs)

There is no obvious reason to think so, and plenty of obvious reasons to think not. --JBL (talk) 21:57, 7 October 2021 (UTC)[reply]

Everything down to Yocto- is specified by International Bureau of Weights and Measures; see Metric prefix. I suspect everything after that is made up. It's doubtful that smaller prefixes would be used often enough be worth naming, or if they were named that people would bother learning them. It's much more useful to use scientific notation for such extreme ratios. --RDBury (talk) 02:05, 8 October 2021 (UTC)[reply]

RDBury, scientific notation combined with yocto- simply cancels out the units and makes them the main units again. For example, "this length is 10^24 yoctometers" becomes "this length is a meter". Scientific notation combined with yotta-, in contrast, makes very large units; for example "10^24 yottameters" is equal to 10^48 meters. Georgia guy (talk) 13:00, 8 October 2021 (UTC)[reply]

The diameter of the observable universe is thought to be 880 Ym, give or take a metre, so a practical need for 10²⁴ Ym is somewhat unlikely to arise. A similar argument could be attempted at the other side of the scale, where 10⁻²⁴ ym equals 10⁻⁴⁸ m. With the Planck length, denoted ℓ_P, being about 16.16255 udm, extension at that side makes more sense, but I find 1.616255 × 10⁻³⁵ m easier to work with. Also, the volume of a Planck cube, ℓ_P³, is about 4.222 × 10⁻¹⁰⁵ m³, so where does it stop? How many extreme prefixes would we have to learn? --Lambiam 17:41, 8 October 2021 (UTC)[reply]

Centillion is a word. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 02:07, 9 October 2021 (UTC)[reply]

Here are more sources: https://www.youtube.com/watch?v=sE3YlA7iyAI which comes from https://trakaplex.wordpress.com/2021/08/07/tier-1-and-upper-tier-2-prefixes/ I actually made all this myself though. If that counts...— Preceding unsigned comment added by Trakaplex (talk • contribs)

Wikipedia is not for things made up one day. --Lambiam 19:08, 12 October 2021 (UTC)[reply]

@Trakaplex: by definition, things you create and upload yourself to YouTube, a blog, etc, are self-published sources (as in, not vetted by any experts) and not allowed on Wikipedia. Please do understand that Wikipedia is an encyclopedia and is not a place to publish original research, or indeed as Lambiam pointed out, things that you have invented. Your user page states you are interested in googology -- there are many existing Wikipedia articles on large numbers that you could consider improving instead (using material cited from reliable sources -- blogs, forums, and personal websites are not it). Best, eviolite (talk) 00:55, 13 October 2021 (UTC)[reply]