File: [local] / OpenXM_contrib2 / asir2000 / lib / solve (download)
Revision 1.3, Tue Aug 22 05:04:23 2000 UTC (24 years, 1 month ago) by noro
Branch: MAIN
CVS Tags: maekawa-ipv6, STABLE_1_1_3, RELEASE_1_2_2, RELEASE_1_2_1, RELEASE_1_1_3 Changes since 1.2: +2 -2
lines
Sorry, the email address in the license agreement was incorrect.
|
/*
* Copyright (c) 1994-2000 FUJITSU LABORATORIES LIMITED
* All rights reserved.
*
* FUJITSU LABORATORIES LIMITED ("FLL") hereby grants you a limited,
* non-exclusive and royalty-free license to use, copy, modify and
* redistribute, solely for non-commercial and non-profit purposes, the
* computer program, "Risa/Asir" ("SOFTWARE"), subject to the terms and
* conditions of this Agreement. For the avoidance of doubt, you acquire
* only a limited right to use the SOFTWARE hereunder, and FLL or any
* third party developer retains all rights, including but not limited to
* copyrights, in and to the SOFTWARE.
*
* (1) FLL does not grant you a license in any way for commercial
* purposes. You may use the SOFTWARE only for non-commercial and
* non-profit purposes only, such as academic, research and internal
* business use.
* (2) The SOFTWARE is protected by the Copyright Law of Japan and
* international copyright treaties. If you make copies of the SOFTWARE,
* with or without modification, as permitted hereunder, you shall affix
* to all such copies of the SOFTWARE the above copyright notice.
* (3) An explicit reference to this SOFTWARE and its copyright owner
* shall be made on your publication or presentation in any form of the
* results obtained by use of the SOFTWARE.
* (4) In the event that you modify the SOFTWARE, you shall notify FLL by
* e-mail at risa-admin@sec.flab.fujitsu.co.jp of the detailed specification
* for such modification or the source code of the modified part of the
* SOFTWARE.
*
* THE SOFTWARE IS PROVIDED AS IS WITHOUT ANY WARRANTY OF ANY KIND. FLL
* MAKES ABSOLUTELY NO WARRANTIES, EXPRESSED, IMPLIED OR STATUTORY, AND
* EXPRESSLY DISCLAIMS ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS
* FOR A PARTICULAR PURPOSE OR NONINFRINGEMENT OF THIRD PARTIES'
* RIGHTS. NO FLL DEALER, AGENT, EMPLOYEES IS AUTHORIZED TO MAKE ANY
* MODIFICATIONS, EXTENSIONS, OR ADDITIONS TO THIS WARRANTY.
* UNDER NO CIRCUMSTANCES AND UNDER NO LEGAL THEORY, TORT, CONTRACT,
* OR OTHERWISE, SHALL FLL BE LIABLE TO YOU OR ANY OTHER PERSON FOR ANY
* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, PUNITIVE OR CONSEQUENTIAL
* DAMAGES OF ANY CHARACTER, INCLUDING, WITHOUT LIMITATION, DAMAGES
* ARISING OUT OF OR RELATING TO THE SOFTWARE OR THIS AGREEMENT, DAMAGES
* FOR LOSS OF GOODWILL, WORK STOPPAGE, OR LOSS OF DATA, OR FOR ANY
* DAMAGES, EVEN IF FLL SHALL HAVE BEEN INFORMED OF THE POSSIBILITY OF
* SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. EVEN IF A PART
* OF THE SOFTWARE HAS BEEN DEVELOPED BY A THIRD PARTY, THE THIRD PARTY
* DEVELOPER SHALL HAVE NO LIABILITY IN CONNECTION WITH THE USE,
* PERFORMANCE OR NON-PERFORMANCE OF THE SOFTWARE.
*
* $OpenXM: OpenXM_contrib2/asir2000/lib/solve,v 1.3 2000/08/22 05:04:23 noro Exp $
*/
def kenzan(El,Sl)
{
for ( Tl = El; Tl != []; Tl = cdr(Tl) ) {
if ( substv(car(Tl),Sl) ) {
print("kenzan : error");
return 0;
}
}
print("kenzan : ok");
return 1;
}
def substv(P,Sl)
{
for ( A = P; Sl != []; Sl = cdr(Sl) )
A = subst(A,car(car(Sl)),car(cdr(car(Sl))));
return A;
}
def co(X,V,D)
{
for ( I = 0; I < D; I++ )
X = diff(X,V);
return sdiv(subst(X,V,0),fac(D));
}
def solve(El,Vl)
/*
* El : list of linear forms
* Vl : list of variable
*/
{
N = length(El); M = length(Vl);
Mat = newmat(N,M+1);
W = newvect(M+1); Index = newvect(N); Vs = newvect(M);
for ( I = 0, Tl = Vl; I < M; Tl = cdr(Tl), I++ )
Vs[I] = car(Tl);
for ( I = 0, Tl = El; I < N; Tl = cdr(Tl), I++ ) {
ltov(car(Tl),Vl,W);
for ( J = 0; J <= M; J++ )
Mat[I][J] = W[J];
}
Tl = solvemain(Mat,Index,N,M); L = car(Tl); D = car(cdr(Tl));
if ( L < 0 )
return [];
for ( I = L - 1, S = []; I >= 0; I-- ) {
for ( J = Index[I]+1, A = 0; J < M; J++ ) {
A += Mat[I][J]*Vs[J];
}
S = cons([Vs[Index[I]],-red((A+Mat[I][M])/D)],S);
}
if ( kenzan(El,S) )
return S;
else
return [];
return S;
}
def solvemain(Mat,Index,N,M)
/*
* Mat : matrix of size Nx(M+1)
* Index : vector of length N
*/
{
for ( J = 0, L = 0, D = 1; J < M; J++ ) {
for ( I = L; I < N && !Mat[I][J]; I++ );
if ( I == N )
continue;
Index[L] = J;
for ( K = 0; K <= M; K++ ) {
T = Mat[I][K]; Mat[I][K] = Mat[L][K]; Mat[L][K] = T;
}
for ( I = L + 1, V = Mat[L][J]; I < N; I++ )
for ( K = J, U = Mat[I][J]; K <= M; K++ )
Mat[I][K] = sdiv(Mat[I][K]*V-Mat[L][K]*U,D);
D = V; L++;
}
for ( I = L; I < N; I++ )
for ( J = 0; J <= M; J++ )
if ( Mat[I][J] )
return -1;
for ( I = L - 2, W = newvect(M+1); I >= 0; I-- ) {
for ( J = 0; J <= M; J++ )
W[J] = 0;
for ( G = I + 1; G < L; G++ )
for ( H = Index[G], U = Mat[I][H]; H <= M; H++ )
W[H] += Mat[G][H]*U;
for ( J = Index[I], U = Mat[I][J]; J <= M; J++ )
Mat[I][J] = sdiv(Mat[I][J]*D-W[J],U);
}
return [L,D];
}
def length(L)
{
for ( I = 0; L != []; L = cdr(L), I++ );
return I;
}
def ltov(P,VL,W)
{
for ( I = 0, L = VL; L != []; L = cdr(L), I++ ) {
W[I] = co(P,car(L),1); P -= W[I]*car(L);
}
W[I] = P;
}
end$