Re: Automatic algorithm optimisation via fast matrix exponentiation

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From	"Nuno Lopes" <nuno.lopes@ist.utl.pt>
Newsgroups	comp.compilers
Subject	Re: Automatic algorithm optimisation via fast matrix exponentiation
Date	Sun, 11 Jan 2015 19:22:03 -0000
Organization	Compilers Central
Lines	20
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<15-01-011@comp.compilers> (permalink)
References	<15-01-010@comp.compilers>
NNTP-Posting-Host	news.iecc.com
Mime-Version	1.0
Content-Type	text/plain; format=flowed; charset="iso-8859-1"; reply-type=original
Content-Transfer-Encoding	8bit
X-Trace	miucha.iecc.com 1421030134 36760 2001:470:1f07:1126:0:676f:7373:6970 (12 Jan 2015 02:35:34 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Mon, 12 Jan 2015 02:35:34 +0000 (UTC)
Keywords	optimize
Posted-Date	11 Jan 2015 21:35:34 EST
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	csiph.com comp.compilers:1468

Show key headers only | View raw

> Lovely article:
>
> http://kukuruku.co/hub/algorithms/automatic-algorithms-optimization-via-fast-matrix-exponentiation
>
> Do any compilers do this kind of thing?

Partially, yes.

For example, LLVM has a quadratic recurrence solver (named SCEV --
scalar evolution).  For this purpose, matrix exponentiation is pretty
much equivalent to recurrence solving.  So, if LLVM manages to rewrite
an induction variable as a recurrence, and if it manages to compute
its closed-form, then LLVM may replace a loop with straight-line code.

I believe GCC and MSVC can do similar things, since it's a somehow required
piece of technology for automatic vectorization, which all compilers can do
to some extent these days..

Nuno

Back to comp.compilers | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Automatic algorithm optimisation via fast matrix exponentiation willvarfar@gmail.com - 2015-01-11 07:18 -0800
  Re: Automatic algorithm optimisation via fast matrix exponentiation "Nuno Lopes" <nuno.lopes@ist.utl.pt> - 2015-01-11 19:22 +0000

csiph-web