Toom-Cook, por vezes conhecido como Toom-3, nomeado em homenagem a Andrei Toom, que introduziu o novo algoritmo com a sua baixa complexidade, e a Stephen Cook, que clarificou a sua descrição, é um algoritmo de multiplicação para inteiros grandes. Dados dois inteiros grandes, a e b, o algoritmo de Toom-Cook divide a e b em k partes menores, cada uma de comprimento l, e executa operações nessas partes. À medida que k cresce, é possível combinar muitas das suboperações de multiplicação, reduzindo assim a complexidade computacional global do algoritmo. As suboperações de multiplicação podem então ser calculadas recursivamente usando novamente a multiplicação de Toom-Cook, e assim por diante. Embora os termos "Toom-3" e "Toom-Cook" sejam por vezes incorretamente utilizados de forma intercambiável, o Toom-3 é apenas uma instância única do algoritmo de Toom-Cook, em que k = 3. O Toom-3 reduz nove multiplicações para cinco, e é executado num tempo de Θ(nlog(5)/log(3)) ≈ Θ(n1.46). Em geral, o Toom-k é executado em Θ(c(k) ne), onde e = log(2k − 1) / log(k), ne é o tempo gasto nas submultiplicações, e c é o tempo despendido nas adições e nas multiplicações por pequenas constantes. O algoritmo de Karatsuba é equivalente ao Toom-2, onde o número é dividido em duas partes menores. Este reduz quatro multiplicações para três e, portanto, opera em Θ(nlog(3)/log(2)) ≈ Θ(n1.58). Embora o expoente e possa ser definido para um valor arbitrariamente próximo de 1 através do aumento de k, o termo constante na função cresce muito rapidamente. A taxa de crescimento para esquemas Toom-Cook de nível misto ainda era um problema de investigação em aberto em 2005. Uma implementação descrita por Donald Knuth atinge a complexidade de tempo Θ(n 2√2 log n log n). Devido à sua sobrecarga (overhead), o algoritmo de Toom-Cook é mais lento do que a multiplicação longa para números pequenos, sendo por isso tipicamente utilizado para multiplicações de tamanho intermédio, antes que o algoritmo de Schönhage-Strassen (com complexidade Θ(n log n log log n)), que é assintoticamente mais rápido, se torne prático. Toom descreveu este algoritmo pela primeira vez em 1963, e Cook publicou um algoritmo melhorado (assintoticamente equivalente) na sua tese de doutoramento em 1966.
Detalhes Esta seção discute exatamente como executar o Toom-k para qualquer valor dado de k, e consiste numa simplificação da descrição da multiplicação de polinómios de Toom-Cook apresentada por Marco Bodrato. O algoritmo possui cinco passos principais:
Divisão (Splitting) Avaliação (Evaluation) Multiplicação pontual (Pointwise multiplication) Interpolação (Interpolation) Recomposição (Recomposition) Numa implementação típica de inteiros grandes, cada número inteiro é representado como uma sequência de dígitos em notação posicional, com a base (radix) definida para um valor b (tipicamente grande); para este exemplo, utilizamos
b = 10000
{\displaystyle b=10000}
, de modo a que cada dígito corresponda a um grupo de quatro dígitos decimais (numa implementação de computador, b seria tipicamente uma potência de 2). Suponhamos que os dois números inteiros a serem multiplicados são:
Estes são muito mais pequenos do que os que seriam normalmente processados com o algoritmo Toom-Cook (a multiplicação escolar seria mais rápida)[carece de fontes]?, mas servirão perfeitamente para ilustrar o algoritmo.
Divisão No Toom-k, queremos dividir os fatores em k partes. O primeiro passo consiste em selecionar a base
B =
b
i
{\displaystyle B=b^{i}}
, de tal forma que o número de dígitos de tanto m quanto n na base B seja, no máximo, k (por exemplo, 3 no Toom-3). Uma escolha típica para i é dada por:
i = max
{
⌊
⌊
log
b
m
⌋
k
⌋
,
⌊
⌊
log
b
n
⌋
k
⌋
}
+ 1.
{\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lfloor \log _{b}m\right\rfloor }{k}}\right\rfloor ,\left\lfloor {\frac {\left\lfloor \log _{b}n\right\rfloor }{k}}\right\rfloor \right\}+1.}
No nosso exemplo, faremos o Toom-3, pelo que escolhemos
B =
b
2
=
10
8
{\displaystyle B=b^{2}=10^{8}}
. De seguida, separamos m e n nos seus dígitos de base B,
m
i
{\displaystyle m_{i}}
e
n
i
{\displaystyle n_{i}}
:
m
2
= 123456
m
1
= 78901234
m
0
= 56789012
n
2
= 98765
n
1
= 43219876
n
0
= 54321098
{\displaystyle {\begin{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}=98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\end{aligned}}}
Usamos então estes dígitos como coeficientes em polinómios p e q de grau
( k − 1 )
{\displaystyle (k-1)}
, com a propriedade de que
p ( B ) = m
{\displaystyle p(B)=m}
e
q ( B ) = n
{\displaystyle q(B)=n}
:
p ( x ) =
m
2
x
2
+
m
1
x +
m
0
= 123456
x
2
+ 78901234 x + 56789012
{\displaystyle p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,}
q ( x ) =
n
2
x
2
+
n
1
x +
n
0
= 98765
x
2
+ 43219876 x + 54321098
{\displaystyle q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}+43219876x+54321098\,}
O objetivo de definir estes polinómios é que, se conseguirmos calcular o seu produto
r ( x ) = p ( x ) q ( x )
{\displaystyle r(x)=p(x)q(x)}
, a nossa resposta final será
r ( B ) = m × n
{\displaystyle r(B)=m\times n}
. No caso em que os números a serem multiplicados são de tamanhos diferentes, é útil utilizar valores diferentes de k para m e n, que chamaremos de
k
m
{\displaystyle k_{m}}
e
k
n
{\displaystyle k_{n}}
. Por exemplo, o algoritmo "Toom-2.5" refere-se ao Toom-Cook com
k
m
= 3
{\displaystyle k_{m}=3}
e
k
n
= 2
{\displaystyle k_{n}=2}
. Neste caso, o i em
B =
b
i
{\displaystyle B=b^{i}}
é tipicamente escolhido por:
i = max
{
⌊
⌈
log
b
m
⌉
k
m
⌋
,
⌊
⌈
log
b
n
⌉
k
n
⌋
}
.
{\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil }{k_{m}}}\right\rfloor ,\left\lfloor {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n}}}\right\rfloor \right\}.}
Avaliação A abordagem de Toom-Cook para calcular o produto polinomial
p ( x ) q ( x )
{\displaystyle p(x)q(x)}
é bastante comum. Note que um polinómio de grau d é determinado de forma única por
d + 1
{\displaystyle d+1}
pontos (por exemplo, uma reta - que é um polinómio de grau um - é especificada por dois pontos). A ideia é avaliar
p ( ⋅ )
{\displaystyle p(\cdot )}
e
q ( ⋅ )
{\displaystyle q(\cdot )}
em vários pontos. Depois, multiplicam-se os seus valores nesses pontos para obter pontos no polinómio produto. Finalmente, interpola-se para encontrar os seus coeficientes.
Uma vez que
deg ( p q ) = deg ( p ) + deg ( q )
{\displaystyle \deg(pq)=\deg(p)+\deg(q)}
, necessitaremos de
deg ( p ) + deg ( q ) + 1 =
k
m
+
k
n
− 1
{\displaystyle \deg(p)+\deg(q)+1=k_{m}+k_{n}-1}
pontos para determinar o resultado final. Designemos este valor por d. No caso do Toom-3,
d = 5
{\displaystyle d=5}
. O algoritmo funcionará independentemente dos pontos que forem escolhidos (com algumas pequenas exceções; veja o requisito de invertibilidade da matriz na secção Interpolação), mas para simplificar o algoritmo, é preferível escolher valores inteiros pequenos como 0, 1, −1 e −2. Um valor de ponto invulgar que é frequentemente utilizado é o infinito, escrito como
∞
{\displaystyle \infty }
ou
1
/
0
{\displaystyle 1/0}
. "Avaliar" um polinómio p no infinito significa, na verdade, calcular o limite de
p ( x )
/
x
deg p
{\displaystyle p(x)/x^{\deg p}}
quando x tende para o infinito. Consequentemente,
p ( ∞ )
{\displaystyle p(\infty )}
é sempre o valor do seu coeficiente de maior grau (no exemplo acima, o coeficiente
m
2
{\displaystyle m_{2}}
). No nosso exemplo do Toom-3, usaremos os pontos 0, 1, −1, −2 e
∞
{\displaystyle \infty }
. Estas escolhas simplificam a avaliação, produzindo as fórmulas:
p ( 0 )
=
m
0
+
m
1
( 0 ) +
m
2
( 0
)
2
=
m
0
p ( 1 )
=
m
0
+
m
1
( 1 ) +
m
2
( 1
)
2
=
m
0
+
m
1
+
m
2
p ( − 1 )
=
m
0
+
m
1
( − 1 ) +
m
2
( − 1
)
2
=
m
0
−
m
1
+
m
2
p ( − 2 )
=
m
0
+
m
1
( − 2 ) +
m
2
( − 2
)
2
=
m
0
− 2
m
1
+ 4
m
2
p ( ∞ )
=
m
2
{\displaystyle {\begin{array}{lrlrl}p(0)&=&m_{0}+m_{1}(0)+m_{2}(0)^{2}&=&m_{0}\\p(1)&=&m_{0}+m_{1}(1)+m_{2}(1)^{2}&=&m_{0}+m_{1}+m_{2}\\p(-1)&=&m_{0}+m_{1}(-1)+m_{2}(-1)^{2}&=&m_{0}-m_{1}+m_{2}\\p(-2)&=&m_{0}+m_{1}(-2)+m_{2}(-2)^{2}&=&m_{0}-2m_{1}+4m_{2}\\p(\infty )&=&m_{2}&&\end{array}}}
e de forma análoga para q. No nosso exemplo, os valores que obtemos são:
Como demonstrado, estes valores podem ser negativos. Para efeitos de explicação posterior, será útil considerar este processo de avaliação como uma multiplicação matriz-vetor, em que cada linha da matriz contém as potências de um dos pontos de avaliação, e o vetor contém os coeficientes do polinómio:
(
p ( 0 )
p ( 1 )
p ( − 1 )
p ( − 2 )
p ( ∞ )
)
=
(
0
0
0
1
0
2
1
0
1
1
1
2
( − 1
)
0
( − 1
)
1
( − 1
)
2
( − 2
)
0
( − 2
)
1
( − 2
)
2
0
0
1
)
(
m
0
m
1
m
2
)
=
(
1
0
0
1
1
1
1
− 1
1
1
− 2
4
0
0
1
)
(
m
0
m
1
m
2
)
.
{\displaystyle \left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix}}\right)=\left({\begin{matrix}0^{0}&0^{1}&0^{2}\\1^{0}&1^{1}&1^{2}\\(-1)^{0}&(-1)^{1}&(-1)^{2}\\(-2)^{0}&(-2)^{1}&(-2)^{2}\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right)=\left({\begin{matrix}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right).}
As dimensões da matriz são d por
k
m
{\displaystyle k_{m}}
para p, e d por
k
n
{\displaystyle k_{n}}
para q. A linha referente ao infinito é sempre constituída apenas por zeros, com a exceção de um 1 na última coluna.
Avaliação mais rápida A avaliação multiponto pode ser obtida de forma mais rápida do que recorrendo às fórmulas acima. O número de operações elementares (adição/subtração) pode ser reduzido. A sequência fornecida por Bodrato para o Toom-3, executada aqui sobre o primeiro operando (polinómio p) do nosso exemplo, é a seguinte:
Esta sequência requer cinco operações de adição/subtração, uma a menos do que na avaliação direta. Além disso, poupou-se a multiplicação por 4 que ocorreria no cálculo de p(−2).
Multiplicação pontual Ao contrário da multiplicação dos polinómios
p ( ⋅ )
{\displaystyle p(\cdot )}
e
q ( ⋅ )
{\displaystyle q(\cdot )}
, a multiplicação dos valores avaliados
p ( a )
{\displaystyle p(a)}
e
q ( a )
{\displaystyle q(a)}
envolve unicamente a multiplicação de números inteiros — consistindo numa instância mais pequena do problema original. Nós invocamos recursivamente o nosso procedimento de multiplicação para multiplicar cada par de pontos avaliados. Em implementações práticas, à medida que os operandos se tornam mais pequenos, o algoritmo muda para a multiplicação longa escolar. Fazendo de r o polinómio produto, no nosso exemplo temos:
Como ilustrado, estes resultados também podem ser negativos. Para números suficientemente grandes, este é o passo mais computacionalmente dispendioso, e o único passo que não é linear em relação ao tamanho de m e n.
Interpolação Este é o passo mais complexo, atuando como o inverso do passo de avaliação: dados os nossos d pontos no polinómio produto
r ( ⋅ )
{\displaystyle r(\cdot )}
, precisamos de determinar os seus coeficientes. Dito de outra forma, queremos resolver esta equação matricial para encontrar o vetor do lado direito:
(
r ( 0 )
r ( 1 )
r ( − 1 )
r ( − 2 )
r ( ∞ )
)
=
(
0
0
0
1
0
2
0
3
0
4
1
0
1
1
1
2
1
3
1
4
( − 1
)
0
( − 1
)
1
( − 1
)
2
( − 1
)
3
( − 1
)
4
( − 2
)
0
( − 2
)
1
( − 2
)
2
( − 2
)
3
( − 2
)
4
0
0
0
0
1
)
(
r
0
r
1
r
2
r
3
r
4
)
=
(
1
0
0
0
0
1
1
1
1
1
1
− 1
1
− 1
1
1
− 2
4
− 8
16
0
0
0
0
1
)
(
r
0
r
1
r
2
r
3
r
4
)
.
{\displaystyle {\begin{aligned}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)&{}=\left({\begin{matrix}0^{0}&0^{1}&0^{2}&0^{3}&0^{4}\\1^{0}&1^{1}&1^{2}&1^{3}&1^{4}\\(-1)^{0}&(-1)^{1}&(-1)^{2}&(-1)^{3}&(-1)^{4}\\(-2)^{0}&(-2)^{1}&(-2)^{2}&(-2)^{3}&(-2)^{4}\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right).\end{aligned}}}
Esta matriz é construída da mesma maneira que a do passo de avaliação, exceto que as suas dimensões são
d × d
{\displaystyle d\times d}
. Poderíamos resolver esta equação recorrendo a uma técnica como a eliminação de Gauss, mas isso seria demasiado pesado. Em alternativa, utilizamos o facto de que, desde que os pontos de avaliação tenham sido escolhidos adequadamente, esta matriz é invertível (veja também a Matriz de Vandermonde), resultando assim em:
(
r
0
r
1
r
2
r
3
r
4
)
=
(
1
0
0
0
0
1
1
1
1
1
1
− 1
1
− 1
1
1
− 2
4
− 8
16
0
0
0
0
1
)
− 1
(
r ( 0 )
r ( 1 )
r ( − 1 )
r ( − 2 )
r ( ∞ )
)
=
(
1
0
0
0
0
1 2
1 3
− 1
1 6
− 2
− 1
1 2
1 2
0
− 1
−
1 2
1 6
1 2
−
1 6
2
0
0
0
0
1
)
(
r ( 0 )
r ( 1 )
r ( − 1 )
r ( − 2 )
r ( ∞ )
)
.
{\displaystyle {\begin{aligned}\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)^{-1}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{3}}&-1&{\tfrac {1}{6}}&-2\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&-1\\-{\tfrac {1}{2}}&{\tfrac {1}{6}}&{\tfrac {1}{2}}&-{\tfrac {1}{6}}&2\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right).\end{aligned}}}
Tudo o que resta é calcular este produto matriz-vetor. Embora a matriz possua frações, os coeficientes resultantes serão sempre números inteiros — logo, tudo isto pode ser executado apenas com aritmética inteira, recorrendo apenas a adições, subtrações e multiplicações/divisões por pequenas constantes. Um dos maiores desafios de conceção no algoritmo Toom-Cook é encontrar uma sequência eficiente de operações para calcular este produto; uma sequência descrita por Bodrato para o Toom-3 é a seguinte, executada aqui com os valores do nosso exemplo:
Neste momento, conhecemos os coeficientes do nosso polinómio produto r:
r ( x ) =
3084841486175176
+
6740415721237444
x
+
3422416581971852
x
2
+
13128433387466
x
3
+
12193131840
x
4
{\displaystyle {\begin{array}{rrrl}r(x)=&&3084841486175176&\\&+&6740415721237444&\!\!\!\!x\\&+&3422416581971852&\!\!\!\!x^{2}\\&+&13128433387466&\!\!\!\!x^{3}\\&+&12193131840&\!\!\!\!x^{4}\end{array}}}
Se tivéssemos usado valores diferentes para
k
m
{\displaystyle k_{m}}
,
k
n
{\displaystyle k_{n}}
ou pontos de avaliação, a matriz e a nossa estratégia de interpolação mudariam; contudo, ela não depende dos valores de entrada, podendo assim ser pré-programada (hard-coded) para qualquer conjunto específico de parâmetros.
Recomposição Por fim, avaliamos
r ( B )
{\displaystyle r(B)}
para extrair a nossa resposta final. Esta operação é simples e direta porque
B
{\displaystyle B}
é uma potência de b, e portanto as multiplicações por potências de
B
{\displaystyle B}
correspondem todas a deslocamentos (shifts) de um número inteiro de dígitos na base b. No exemplo que seguimos,
b =
10
4
{\displaystyle b=10^{4}}
e
B =
b
2
=
10
8
{\displaystyle B=b^{2}=10^{8}}
.
E este é exatamente o produto de 1234567890123456789012 e 987654321987654321098.
Divisão assimétrica A etapa de interpolação depende do grau do polinômio produto, que é a soma dos graus dos polinômios fatores, mas não dos graus individuais. Embora o Toom-3 básico divida cada fator em 3 partes (polinômios quadráticos), se os fatores diferirem em tamanho, pode ser benéfico dividir um em 2 partes (um polinômio linear) e o outro em 4 partes (um cúbico) com coeficientes de tamanho mais equilibrado. Assim, a mesma etapa de interpolação pode produzir um polinômio produto quártico. Para o Toom-3, esta é a única divisão alternativa interessante (o caso degenerado de dividir qualquer um dos fatores em apenas 1 parte não oferece economia de tempo), mas o Toom-Cook de grau mais elevado permite possibilidades adicionais. Além dos casos de divisão em partes iguais, é possível ter casos semi-inteiros que são sempre assimétricos; o número total de partes é ímpar e o grau do polinômio produto é par. Por exemplo, o Toom-2.5 divide um fator em 2 partes e o outro em 3, enquanto o Toom-3.5 pode dividir os fatores como 2+5 ou 3+4.
Matrizes de interpolação para vários k Aqui apresentamos matrizes de interpolação comuns para alguns valores pequenos comuns e diferentes de
k
m
{\displaystyle k_{m}}
e
k
n
{\displaystyle k_{n}}
.
Toom-1 Aplicando formalmente a definição, podemos considerar o Toom-1 (
k
m
=
k
n
= 1
{\displaystyle k_{m}=k_{n}=1}
). Isto não produz um algoritmo de multiplicação, mas sim um algoritmo recursivo que nunca para, uma vez que reduz trivialmente cada instância de entrada a uma chamada recursiva com a mesma instância. O algoritmo requer 1 ponto de avaliação, cujo valor é irrelevante, visto que é utilizado apenas para "avaliar" polinómios constantes. Assim, a matriz de interpolação é a matriz identidade:
(
1
)
− 1
=
(
1
)
.
{\displaystyle \left({\begin{matrix}1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1\end{matrix}}\right).}
Toom-1.5 O Toom-1.5 (
k
m
= 2
{\displaystyle k_{m}=2}
,
k
n
= 1
{\displaystyle k_{n}=1}
) continua a ser degenerado: reduz recursivamente uma entrada dividindo o seu tamanho a meio, mas deixa a outra entrada inalterada, pelo que só o podemos transformar num algoritmo de multiplicação se fornecermos um algoritmo de multiplicação
1 × n
{\displaystyle 1\times n}
como caso base (enquanto que o verdadeiro algoritmo de Toom-Cook se reduz a casos base de tamanho constante). Requer 2 pontos de avaliação, aqui escolhidos como sendo 0 e
∞
{\displaystyle \infty }
. A sua matriz de interpolação é então a matriz identidade:
(
1
0
0
1
)
− 1
=
(
1
0
0
1
)
.
{\displaystyle \left({\begin{matrix}1&0\\0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0\\0&1\end{matrix}}\right).}
O algoritmo é essencialmente equivalente a uma forma de multiplicação longa: ambos os coeficientes de um fator são multiplicados pelo único coeficiente do outro fator.
Toom-2 O Toom-2 (
k
m
= 2
{\displaystyle k_{m}=2}
,
k
n
= 2
{\displaystyle k_{n}=2}
) requer 3 pontos de avaliação, aqui escolhidos como sendo 0, 1 e
∞
{\displaystyle \infty }
. É o mesmo que a multiplicação de Karatsuba, com uma matriz de interpolação de:
(
1
0
0
1
1
1
0
0
1
)
− 1
=
(
1
0
0
− 1
1
− 1
0
0
1
)
.
{\displaystyle \left({\begin{matrix}1&0&0\\1&1&1\\0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0\\-1&1&-1\\0&0&1\end{matrix}}\right).}
Toom-2.5 O Toom-2.5 (
k
m
= 3
{\displaystyle k_{m}=3}
,
k
n
= 2
{\displaystyle k_{n}=2}
) requer 4 pontos de avaliação, aqui escolhidos como sendo 0, 1, -1 e
∞
{\displaystyle \infty }
. Possui então uma matriz de interpolação de:
(
1
0
0
0
1
1
1
1
1
− 1
1
− 1
0
0
0
1
)
− 1
=
(
1
0
0
0
0
1 2
−
1 2
− 1
− 1
1 2
1 2
0
0
0
0
1
)
.
{\displaystyle \left({\begin{matrix}1&0&0&0\\1&1&1&1\\1&-1&1&-1\\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0&0\\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0\\0&0&0&1\end{matrix}}\right).}
Referências