A google scholar search turns up several papers on parallel interior point methods.
> On 03/27/2021 9:16 AM Reginald Beardsley <[email protected]> wrote: > > > Thank you. I'd not seen that, however, my question is really more > literature oriented at the moment. A quick look at the presentation on the > page reveals that it has all the issues that limit the simplex method in > general. > > With apologies for my lexical abuses to those who are better > mathematicians than I: > > For instances of Ax=y where x is sparse, i.e. has few non-zero elements, > there is an identity that spans a large number of problems in a wide variety > of mathematical disciplines ranging from linear algebra to computational > geometry and graph theory. > > This paper by David Donoho: > > https://statistics.stanford.edu/sites/g/files/sbiybj6031/f/2005-04.pdf > > along with this: > > https://statistics.stanford.edu/sites/g/files/sbiybj6031/f/2004-09.pdf > > is the motivation for my quest. The 2nd paper I regard as the single most > important paper in applied mathematics since Norbert Wiener's "yellow peril". > Working in reflection seismic research I often encountered practical problems > from computational geometry, many of which are NP hard. For obvious reasons, > I feared those greatly. So much so that when some new problem was presented > to me, my first question was, "Is it NP?" > > Donoho's 2004-09 is the single instance of which I am aware of a solution > in tractable time of a problem which is NP hard at first glance. His 2005-04 > hints at the possibility of a trivially parallel solution via computational > geometry, graph theory or some homomorph of those. I saw a little twinkle > when I was using GLPK to solve inverse problems based on the heat equation > using basis pursuit. One day I realized I was solving problems I'd been > taught could not be solved as Donoho discusses in the introduction to > 2004-09. That led me on a 3 year journey through some 3000 pages of > mathematics which eventually reached Grunbaum's monograph on regular > polytopes in N-dimensional space. Rather a long journey for someone with a BA > in English lit. The systems on ebay reminded me of that little twinkle. > > Having read this list for many years now, it is the only place I can > think of to ask about such things. > > Have Fun! > Reg > > > On Saturday, March 27, 2021, 02:52:43 AM CDT, Domingo Alvarez Duarte > <[email protected]> wrote: > > > Hello Reginald ! > > Have looked at https://github.com/ERGO-Code/HiGHS > https://github.com/ERGO-Code/HiGHS they seem to be doing > a parallel LP solver. > > Cheers ! > > On 26/3/21 21:26, Reginald Beardsley wrote: > > I haven't fooled around with GLPK and LP problems in general for > several years now. > > > > The appearance of off lease machines with 28+ cores, 256 GB of RAM > for almost nothing has me wondering what the general state of the art is in > parallelizable algorithms for solving LP and related problems. > > > > I have "Computational Techniques of the Simplex Method" by Istvan > Maros. Unfortunately, the simplex method is not very amenable to multicore > solution. > > > > My attempt to locate recent work via google scholar was not very > productive, so I thought I'd ask here. Can anyone suggest recent papers or > books germane to the topic? The little I did find was rather old. > > > > Thanks, > > Reg > > > >
