Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Solve Matrix Equation AX=XB
Date: Thu, 26 Apr 2012 18:53:07 +0000 (UTC)
Organization: Xoran Technologies
Lines: 40
Message-ID: <jnc5ij\$blf\$1@newscl01ah.mathworks.com>
References: <h16ekh\$26u\$1@fred.mathworks.com> <h16fq1\$gqn\$1@fred.mathworks.com> <h16jq4\$a79\$1@fred.mathworks.com>
NNTP-Posting-Host: www-01-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: newscl01ah.mathworks.com 1335466387 11951 172.30.248.46 (26 Apr 2012 18:53:07 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 26 Apr 2012 18:53:07 +0000 (UTC)
Xref: news.mathworks.com comp.soft-sys.matlab:766056

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h16jq4\$a79\$1@fred.mathworks.com>...
> n = length(A);
> G = kron(eye(n),A)-kron(B.',eye(n));
> x = null(G)
>
> % reshaping each column of x to (n x n) matrix X will provide a basis-element of the space of solutions.
===============

When B is non-singular (you could do something similar if A is as well), the approach below using generalized eigendecomposition gives much faster results. However, it seems to be because the NULL command is really inefficient. Maybe because NULL is M-coded?

%fake data
N=40;
[Q,R]=qr(rand(N));
A=Q'*diag(0:N-1)*Q;
[Q,R]=qr(rand(N));
B=Q'*diag(1:N)*Q;

tic;
n = length(A);
G = kron(eye(n),A)-kron(B.',eye(n));
x1 = null(G);
toc
%Elapsed time is 5.129806 seconds.

tic;
n=length(A);
[Va,Da]=eig(A,eye(n));
[Vb,Db]=eig(eye(n),B.');

V=kron(Vb,Va);
D=kron(diag(Db),diag(Da));

idx=find( abs(D-1)<=1e-6*max(D));

x2=V(:,idx);

toc;
%Elapsed time is 0.050615 seconds.