Úkol 3

Úkolem je implementovat efektivní maticové operace (např. +, -, *) pro dva speciální typy matic; diagonální matice a jednotková matice {“identity”}. Toho dosáhneme tak, že implementujeme nové metody pro tyto typy, které budou využívat speciální formu daných matic. Vaším úkolem je implementovat následující typy:

• Diagonal,
• Identity.

Budeme pracovat pouze s 2D čtvercovými maticemi. Oba nové typy proto implementujte jako podtypy AbstractMatrix{T} (jak je uvedeno v šabloně). Všimněte si, že typ AbstractMatrix{T} je alias pro AbstractArray{T, 2}.

struct Diagonal{T} <: AbstractMatrix{T}
struct Identity{T} <: AbstractMatrix{T}

Implementujte typy tak, aby mohly být vytvořeny následovně:

d = [1, 2, 3]   # diagonála
D = Diagonal(d) # diagonální matice s diagonálou `d`
 
n = 3
I = Identity(n) # jednotková matice velikosti `n` 

Pro oba typy implementujte nové metody pro následující funkce z modulu Base pro práci s maticemi (jak je uvedeno v šabloně):

• getindex: pro indexy i, j vrátí odpovídající prvek,
• size: vrátí n-tici rozměrů matice.

Pokud tyto dvě metody správně implementujete pro naše speciální typy matic, některé základní operace již budou fungovat. Například sčítání dvou diagonálních matic bude fungovat díky tomu, že jsme nové typy definovaly jako podtypy AbstractArray, pro kterou už jsou definované základní metody pro tyto operace. Tyto metody ale nebudou efektivní, jelikož nevyužívají speciální formy našich matic.

d = Diagonal(...)
d + d  # funguje

Dále implementujte i další metody z Base:

• sum: vrátí součet všech prvků matice,
• convert: funguje pro Diagonal a Identity stejně jako pro běžné matice (např. convert(Matrix{Float32}, [1 2; 3 4]) převede původní matici typu Matrix{Float64} na Matrix{Float32}).

Navíc implementujte následující operace s maticemi:

• diagonal: vrátí diagonálu jako vektor,
• trace: vrátí stopu matice.

Nezapomeňte tyto funkce implementovat také pro původní typ Matrix.

Poté definujte funkce Base +, -, * pro oba nové typy matic, podobně jako existují metody typu (+)(x::Matrix, y::Matrix). Implementujte +, -, *:

• pro všechny kombinace maticových vstupů {+,-,*},
• pro matici a vektor {jen *},
• pro matici a skalár (jen *).

Neimplementujte {element-wise} varianty s broadcastingem.

Každá metoda by měla být implementována co nejefektivněji z hlediska výpočtu. Zajistěte také, aby návratový typ byl správný, tedy že součet dvou instancí Diagonal je Diagonal, zatímco součet Matrix a Diagonal má být typu Matrix. Matice by měly být typově stabilní a řídit se standardními pravidly pro propagaci typů (např. promote(Int64, Float64) = Float64).

Nakonec implementujte doplňující konstruktory pro převod mezi typy, kde to dává smysl:

• Diagonal(::AbstractMatrix) vrátí Diagonal matici obsahující pouze diagonální prvky původní matice,
• Matrix(::Diagonal) vytvoří běžnou matici se stejnou diagonálou a nulami mimo ni,
• Matrix(::Identity) vytvoří běžnou jednotkovou matici s jedničkami na diagonále a nulami mimo ni.

Budou prováděny tři kategorie testů:

• úplnost: všechny metody jsou implementovány pro všechny typy,
• správnost: metody vracejí správné výsledky (a správné typy výstupů),
• efektivita: metody jsou výpočetně efektivní a využívají vlastnosti příslušného typu matice (některé metody budou časovány a benchmarkovány).

Pamatujte, že máte omezený počet odevzdání a při implementaci může nastat mnoho chyb. Ujistěte se proto, že své typy a metody důkladně testujete a přemýšlíte předem.

Obecně se snažte vracet co nejjednodušší možný typ matice. Představte si hierarchii Identity < Diagonal < Matrix. Pokud vaše funkce vrací matici, která je diagonálního charakteru (prvky mimo diagonálu jsou nulové), měli byste vrátit typ Diagonal.

Otestujte, které metody po implementaci základní funkcionality už fungují správně (a vracejí správný výstup), abyste je nemuseli psát ručně a zbytečně tak nezvyšovali šanci na chyby. Přemýšlejte ale nad tím, jestli jsou tyto základní metody efektivní, nebo jestli byste měli implementovat nové specializované metody.

Můžete také použít balíček BenchmarkTools.jl k měření výkonu vašich metod, například ve srovnání s běžnými maticovými operacemi. Můžete porovnat i s balíčkem LinearAlgebra, ale neočekává se od vás stejný výkon. Cílem je být rychlejší u operací s Diagonal než při práci s plnou maticí, která má nulové prvky mimo diagonálu. Vaše specializované metody by měly být efektivnější z hlediska asymptotické složitosti - nejde jen o lineární zrychlení. Při testování s dostatečně velkými maticemi byste tedy měli pozorovat výrazné zrychlení.