Skip to main content

qualia_core_db/specialized_libs/linear_algebra/
optimization.rs

1use std::collections::HashMap;
2
3use super::computation::*;
4use super::core_types::*;
5use super::storage::AccessPattern;
6
7/// Optimization engine for matrix operations
8pub struct OptimizationEngine {
9    pub optimizer: MatrixOptimizer,
10    pub analyzer: MatrixAnalyzer,
11    pub transformer: MatrixTransformer,
12}
13
14/// Matrix optimizer
15pub struct MatrixOptimizer {
16    pub optimization_strategies: Vec<OptimizationStrategy>,
17    pub optimization_history: Vec<OptimizationRecord>,
18}
19
20/// Optimization strategies
21#[derive(Debug, Clone, PartialEq)]
22pub enum OptimizationStrategy {
23    CacheOptimization,
24    MemoryLayoutOptimization,
25    AlgorithmSelection,
26    Parallelization,
27    Vectorization,
28    Fusion,
29}
30
31/// Optimization record
32#[derive(Debug, Clone)]
33pub struct OptimizationRecord {
34    pub timestamp: u64,
35    pub matrix_id: String,
36    pub strategy: OptimizationStrategy,
37    pub performance_improvement: f64,
38    pub memory_reduction: f64,
39}
40
41/// Matrix analyzer
42pub struct MatrixAnalyzer {
43    pub analysis_algorithms: Vec<AnalysisAlgorithm>,
44    pub pattern_recognition: PatternRecognition,
45}
46
47/// Analysis algorithms
48#[derive(Debug, Clone, PartialEq)]
49pub enum AnalysisAlgorithm {
50    SparsityAnalysis,
51    StructureAnalysis,
52    AccessPatternAnalysis,
53    PerformanceAnalysis,
54}
55
56/// Pattern recognition
57pub struct PatternRecognition {
58    pub recognized_patterns: Vec<MatrixPattern>,
59    pub pattern_library: PatternLibrary,
60}
61
62/// Matrix patterns
63#[derive(Debug, Clone, PartialEq, Eq, Hash)]
64pub enum MatrixPattern {
65    Diagonal,
66    Triangular,
67    Banded,
68    Symmetric,
69    PositiveDefinite,
70    Orthogonal,
71    Sparse,
72    Dense,
73    BlockDiagonal,
74    Toeplitz,
75    Hankel,
76    Circulant,
77}
78
79/// Pattern library
80pub struct PatternLibrary {
81    pub patterns: HashMap<String, MatrixPattern>,
82    pub optimization_hints: HashMap<MatrixPattern, OptimizationHint>,
83}
84
85/// Optimization hints
86#[derive(Debug, Clone)]
87pub struct OptimizationHint {
88    pub preferred_algorithm: String,
89    pub memory_layout: StorageFormat,
90    pub parallelization_strategy: String,
91    pub vectorization_hints: Vec<String>,
92    /// Estimated speedup factor (e.g. 2.0 = 2x faster than naive)
93    pub estimated_speedup: f64,
94}
95
96/// Matrix transformer
97pub struct MatrixTransformer {
98    pub transformation_rules: Vec<TransformationRule>,
99    pub transformation_history: Vec<TransformationRecord>,
100}
101
102/// Transformation rules
103#[derive(Debug, Clone, PartialEq)]
104pub enum TransformationRule {
105    RowColumnSwap,
106    BlockReordering,
107    DataTypeConversion,
108    CompressionDecompression,
109    LayoutConversion,
110}
111
112/// Transformation record
113#[derive(Debug, Clone)]
114pub struct TransformationRecord {
115    pub timestamp: u64,
116    pub matrix_id: String,
117    pub transformation: TransformationRule,
118    pub performance_impact: f64,
119}
120
121/// Target memory layout for a `MatrixTransformer` layout conversion.
122///
123/// The `Matrix.data` buffer is always a flat `Vec<f64>`; the layout describes
124/// how logical element `(i, j)` is addressed within that buffer. Converting
125/// between layouts reorganises the buffer in place and updates
126/// `Matrix.storage_format` accordingly.
127#[derive(Debug, Clone, PartialEq)]
128pub enum MatrixLayout {
129    /// Row-major storage: element `(i, j)` lives at `data[i * cols + j]`.
130    /// This is the canonical layout used throughout the linear-algebra
131    /// library and the default for sequential row-wise access.
132    RowMajor,
133    /// Column-major storage: element `(i, j)` lives at `data[j * rows + i]`.
134    /// Preferred for column-heavy (strided) access patterns.
135    ColMajor,
136    /// Cache-friendly blocked (tiled) storage. The matrix is partitioned into
137    /// `block_size` x `block_size` sub-blocks. Blocks themselves are laid out
138    /// in row-major block order (block row, then block column); within each
139    /// block the element order follows `inner` (typically `RowMajor`).
140    ///
141    /// Edge blocks that fall outside the matrix dimensions contain only the
142    /// valid elements, so the total buffer length remains `rows * cols`.
143    Blocked(Box<MatrixLayout>, usize),
144    /// SIMD-packed storage: each row is zero-padded to a multiple of
145    /// `SIMD_WIDTH` so that a full SIMD vector load never crosses a row
146    /// boundary. Element `(i, j)` lives at `data[i * stride + j]` where
147    /// `stride = ceil(cols / SIMD_WIDTH) * SIMD_WIDTH`; padding slots are `0.0`.
148    Packed,
149}
150
151/// SIMD vector width (in `f64` elements) used by the [`MatrixLayout::Packed`]
152/// layout. The value `4` corresponds to a 256-bit AVX2 register holding four
153/// double-precision lanes.
154const SIMD_WIDTH: usize = 4;
155
156impl OptimizationEngine {
157    /// Constructs the engine with a fresh optimizer, analyzer, and
158    /// transformer.
159    pub fn new() -> Self {
160        Self {
161            optimizer: MatrixOptimizer::new(),
162            analyzer: MatrixAnalyzer::new(),
163            transformer: MatrixTransformer::new(),
164        }
165    }
166
167    /// Initializes the optimizer, analyzer, and transformer in order.
168    pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
169        self.optimizer.initialize()?;
170        self.analyzer.initialize()?;
171        self.transformer.initialize()?;
172        Ok(())
173    }
174
175    /// Analyzes left and right operands to dynamically select the optimal multiplication
176    /// strategy (AlgorithmSelection for sparse/structural patterns, Parallelization for large compute,
177    /// CacheOptimization for tiled blocks, Vectorization for SIMD) consulting the PatternLibrary hints,
178    /// enforcing the enabled `optimization_strategies` registry, and computing an expected speedup factor
179    /// recorded in optimization history.
180    pub fn optimize_multiplication(
181        &mut self,
182        left: &Matrix,
183        right: &Matrix,
184    ) -> Result<OptimizedMultiplication, LinearAlgebraError> {
185        let left_analysis = self.analyzer.analyze_matrix(left)?;
186        let right_analysis = self.analyzer.analyze_matrix(right)?;
187
188        let max_sparsity = left_analysis.sparsity.max(right_analysis.sparsity);
189        let total_flops = (left.rows * left.cols * right.cols) as f64;
190
191        // Check if any detected structural pattern in left or right operands has a specialized hint
192        let mut best_hint: Option<(MatrixPattern, OptimizationHint)> = None;
193        for pat in left_analysis
194            .detected_patterns
195            .iter()
196            .chain(right_analysis.detected_patterns.iter())
197        {
198            if *pat != MatrixPattern::Dense {
199                if let Some(hint) = self
200                    .analyzer
201                    .pattern_recognition
202                    .pattern_library
203                    .get_optimization_hint(pat)
204                {
205                    if let Some((_, ref current_best)) = best_hint {
206                        if hint.estimated_speedup > current_best.estimated_speedup {
207                            best_hint = Some((pat.clone(), hint.clone()));
208                        }
209                    } else {
210                        best_hint = Some((pat.clone(), hint.clone()));
211                    }
212                }
213            }
214        }
215
216        let (candidate_strategy, candidate_gain) = if let Some((pattern, hint)) = best_hint {
217            // Specialized algorithm selection driven by detected structural pattern
218            let gain = if pattern == MatrixPattern::Sparse {
219                (1.0 / (1.0 - max_sparsity)).max(hint.estimated_speedup).min(15.0)
220            } else {
221                hint.estimated_speedup
222            };
223            (OptimizationStrategy::AlgorithmSelection, gain)
224        } else if max_sparsity >= 0.70 {
225            // Highly sparse: select sparse traversal algorithm
226            let gain = (1.0 / (1.0 - max_sparsity)).min(15.0);
227            (OptimizationStrategy::AlgorithmSelection, gain)
228        } else if total_flops >= 1024.0 * 1024.0 || left.rows >= 512 {
229            // Large dense matrix: multi-threaded parallelization
230            let cores = num_cpus::get().min(8) as f64;
231            let gain = (cores * 0.75).max(1.5);
232            (OptimizationStrategy::Parallelization, gain)
233        } else if left.rows >= 64 && left.cols >= 64 {
234            // Medium matrix: cache blocking and memory layout optimization
235            (OptimizationStrategy::CacheOptimization, 2.5)
236        } else {
237            // Small or vector-like: SIMD vectorization lane utilization
238            let simd_width = match left.metadata.data_type {
239                DataType::Float32 => 4.0, // 4 floats per 128-bit SIMD lane
240                DataType::Float64 => 2.0, // 2 doubles per 128-bit SIMD lane
241                _ => 2.0,
242            };
243            (OptimizationStrategy::Vectorization, simd_width)
244        };
245
246        // Resolve candidate against registered/enabled strategies in MatrixOptimizer
247        let fallbacks = [
248            OptimizationStrategy::CacheOptimization,
249            OptimizationStrategy::Vectorization,
250            OptimizationStrategy::Parallelization,
251            OptimizationStrategy::AlgorithmSelection,
252            OptimizationStrategy::MemoryLayoutOptimization,
253        ];
254        let strategy = self
255            .optimizer
256            .resolve_strategy(candidate_strategy.clone(), &fallbacks)?;
257
258        let expected_gain = if strategy == candidate_strategy {
259            candidate_gain
260        } else {
261            // Strategy was downgraded because candidate is not enabled in optimizer registry
262            match strategy {
263                OptimizationStrategy::AlgorithmSelection => 3.0,
264                OptimizationStrategy::Parallelization => (num_cpus::get().min(8) as f64 * 0.75).max(1.5),
265                OptimizationStrategy::CacheOptimization => 2.5,
266                OptimizationStrategy::Vectorization => 2.0,
267                OptimizationStrategy::MemoryLayoutOptimization => 1.8,
268                OptimizationStrategy::Fusion => 2.0,
269            }
270        };
271
272        // Record the optimization in history
273        let timestamp = std::time::SystemTime::now()
274            .duration_since(std::time::UNIX_EPOCH)
275            .unwrap_or_default()
276            .as_secs();
277        self.optimizer.optimization_history.push(OptimizationRecord {
278            timestamp,
279            matrix_id: format!("{}_x_{}", left.matrix_id, right.matrix_id),
280            strategy: strategy.clone(),
281            performance_improvement: expected_gain,
282            memory_reduction: if strategy == OptimizationStrategy::AlgorithmSelection {
283                max_sparsity * 100.0
284            } else {
285                0.0
286            },
287        });
288
289        // Create optimized operation
290        let optimized = OptimizedMultiplication {
291            left: left.clone(),
292            right: right.clone(),
293            optimization_strategy: strategy,
294            expected_performance_gain: expected_gain,
295        };
296
297        Ok(optimized)
298    }
299}
300
301impl MatrixOptimizer {
302    /// Registers enabled optimization strategies and an empty history.
303    pub fn new() -> Self {
304        Self {
305            optimization_strategies: vec![
306                OptimizationStrategy::AlgorithmSelection,
307                OptimizationStrategy::Vectorization,
308                OptimizationStrategy::CacheOptimization,
309                OptimizationStrategy::Parallelization,
310                OptimizationStrategy::MemoryLayoutOptimization,
311                OptimizationStrategy::Fusion,
312            ],
313            optimization_history: Vec::new(),
314        }
315    }
316
317    /// No-op — there is no optimizer state to prepare.
318    pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
319        Ok(())
320    }
321
322    /// Register an optimization strategy if not already present.
323    pub fn register_strategy(&mut self, strategy: OptimizationStrategy) {
324        if !self.optimization_strategies.contains(&strategy) {
325            self.optimization_strategies.push(strategy);
326        }
327    }
328
329    /// Unregister / disable an optimization strategy.
330    pub fn unregister_strategy(&mut self, strategy: &OptimizationStrategy) {
331        self.optimization_strategies.retain(|s| s != strategy);
332    }
333
334    /// Check if a specific optimization strategy is currently enabled.
335    pub fn is_strategy_enabled(&self, strategy: &OptimizationStrategy) -> bool {
336        self.optimization_strategies.contains(strategy)
337    }
338
339    /// Resolves an optimization strategy by checking if `preferred` is enabled,
340    /// otherwise trying each fallback in order, or returning the first enabled strategy.
341    /// Fails closed if no strategies are enabled.
342    pub fn resolve_strategy(
343        &self,
344        preferred: OptimizationStrategy,
345        fallbacks: &[OptimizationStrategy],
346    ) -> Result<OptimizationStrategy, LinearAlgebraError> {
347        if self.is_strategy_enabled(&preferred) {
348            return Ok(preferred);
349        }
350        for fallback in fallbacks {
351            if self.is_strategy_enabled(fallback) {
352                return Ok(fallback.clone());
353            }
354        }
355        if let Some(first) = self.optimization_strategies.first() {
356            return Ok(first.clone());
357        }
358        Err(LinearAlgebraError::OptimizationError(
359            "No optimization strategies are enabled in MatrixOptimizer".to_string(),
360        ))
361    }
362}
363
364impl MatrixAnalyzer {
365    /// Constructs an analyzer with structure+sparsity algorithms and a fresh
366    /// pattern-recognition registry.
367    pub fn new() -> Self {
368        Self {
369            analysis_algorithms: vec![
370                AnalysisAlgorithm::StructureAnalysis,
371                AnalysisAlgorithm::SparsityAnalysis,
372            ],
373            pattern_recognition: PatternRecognition::new(),
374        }
375    }
376
377    /// Initializes the inner pattern-recognition library (populates the
378    /// pattern/hint maps).
379    pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
380        self.pattern_recognition.initialize()?;
381        Ok(())
382    }
383
384    /// Analyze a matrix: detect all structural patterns, compute sparsity,
385    /// and determine recommended algorithms from optimization hints.
386    pub fn analyze_matrix(
387        &mut self,
388        matrix: &Matrix,
389    ) -> Result<MatrixAnalysis, LinearAlgebraError> {
390        let detected = self.detect_structure(matrix);
391        let sparsity = self.calculate_sparsity(matrix);
392
393        // Record recognized patterns into the PatternRecognition registry
394        for pattern in &detected {
395            if !self.pattern_recognition.recognized_patterns.contains(pattern) {
396                self.pattern_recognition.recognized_patterns.push(pattern.clone());
397            }
398        }
399
400        // Determine recommended algorithms from optimization hints
401        let mut recommended_algorithms = Vec::new();
402        let mut hint_strings = Vec::new();
403        for pattern in &detected {
404            if let Some(hint) = self
405                .pattern_recognition
406                .pattern_library
407                .get_optimization_hint(pattern)
408            {
409                recommended_algorithms.push(hint.preferred_algorithm.clone());
410                hint_strings.push(format!(
411                    "{:?}: {} (speedup ~{:.1}x)",
412                    pattern, hint.preferred_algorithm, hint.estimated_speedup
413                ));
414            }
415        }
416
417        // Pick the primary structure: prefer the most specific pattern
418        let structure = detected.first().cloned().unwrap_or(MatrixPattern::Dense);
419
420        Ok(MatrixAnalysis {
421            matrix_id: matrix.matrix_id.clone(),
422            sparsity,
423            structure,
424            detected_patterns: detected,
425            access_pattern: AccessPattern::Sequential,
426            optimization_hints: hint_strings,
427            recommended_algorithms,
428        })
429    }
430
431    /// Fraction of elements with `|x| <= 1e-10` (1.0 = all-zero). Returns 0.0
432    /// for an empty buffer.
433    fn calculate_sparsity(&self, matrix: &Matrix) -> f64 {
434        let non_zero = matrix.data.iter().filter(|&&x| x.abs() > 1e-10).count();
435        1.0 - (non_zero as f64 / matrix.data.len().max(1) as f64)
436    }
437
438    /// Detect ALL applicable structural patterns in the matrix.
439    /// Uses a tolerance of 1e-10 for floating-point comparisons.
440    pub fn detect_structure(&self, matrix: &Matrix) -> Vec<MatrixPattern> {
441        const TOL: f64 = 1e-10;
442        let rows = matrix.rows;
443        let cols = matrix.cols;
444        let data = &matrix.data;
445        let mut patterns = Vec::new();
446
447        // Helper: get element (i, j)
448        let at = |i: usize, j: usize| -> f64 { data[i * cols + j] };
449
450        // --- Sparse: fraction of non-zero elements < 0.3 ---
451        let non_zero_count = data.iter().filter(|&&x| x.abs() > TOL).count();
452        let total = data.len();
453        let non_zero_frac = if total > 0 {
454            non_zero_count as f64 / total as f64
455        } else {
456            0.0
457        };
458        let is_sparse = non_zero_frac < 0.3;
459        if is_sparse {
460            patterns.push(MatrixPattern::Sparse);
461        }
462
463        // Only square matrices can be diagonal, triangular, symmetric, etc.
464        let is_square = rows == cols && rows > 0;
465
466        // --- Diagonal: all off-diagonal elements are ~0 ---
467        if is_square {
468            let mut is_diagonal = true;
469            for i in 0..rows {
470                for j in 0..cols {
471                    if i != j && at(i, j).abs() > TOL {
472                        is_diagonal = false;
473                        break;
474                    }
475                }
476                if !is_diagonal {
477                    break;
478                }
479            }
480            if is_diagonal {
481                patterns.push(MatrixPattern::Diagonal);
482            }
483        }
484
485        // --- Triangular (Upper/Lower) ---
486        if is_square {
487            // Upper triangular: all elements below diagonal are ~0
488            let mut is_upper = true;
489            for i in 1..rows {
490                for j in 0..i {
491                    if at(i, j).abs() > TOL {
492                        is_upper = false;
493                        break;
494                    }
495                }
496                if !is_upper {
497                    break;
498                }
499            }
500            // Lower triangular: all elements above diagonal are ~0
501            let mut is_lower = true;
502            for i in 0..rows {
503                for j in (i + 1)..cols {
504                    if at(i, j).abs() > TOL {
505                        is_lower = false;
506                        break;
507                    }
508                }
509                if !is_lower {
510                    break;
511                }
512            }
513            if is_upper || is_lower {
514                patterns.push(MatrixPattern::Triangular);
515            }
516        }
517
518        // --- Symmetric: matrix == transpose (within tolerance) ---
519        if is_square {
520            let mut is_symmetric = true;
521            for i in 0..rows {
522                for j in (i + 1)..cols {
523                    if (at(i, j) - at(j, i)).abs() > TOL {
524                        is_symmetric = false;
525                        break;
526                    }
527                }
528                if !is_symmetric {
529                    break;
530                }
531            }
532            if is_symmetric {
533                patterns.push(MatrixPattern::Symmetric);
534
535                // --- PositiveDefinite: symmetric + all eigenvalues > 0 ---
536                // Use Sylvester's criterion: all leading principal minors > 0
537                if Self::is_positive_definite(rows, data, TOL) {
538                    patterns.push(MatrixPattern::PositiveDefinite);
539                }
540            }
541        }
542
543        // --- Banded: non-zero only within a band around diagonal ---
544        if rows > 0 && cols > 0 {
545            let max_dim = rows.max(cols);
546            // Determine the bandwidth
547            let mut bandwidth = 0usize;
548            for i in 0..rows {
549                for j in 0..cols {
550                    if at(i, j).abs() > TOL {
551                        let dist = if i >= j { i - j } else { j - i };
552                        if dist > bandwidth {
553                            bandwidth = dist;
554                        }
555                    }
556                }
557            }
558            // Banded if bandwidth is small relative to matrix dimension
559            // and bandwidth > 0 (not purely diagonal)
560            if bandwidth > 0 && (bandwidth as f64) < (max_dim as f64) / 3.0 {
561                patterns.push(MatrixPattern::Banded);
562            }
563        }
564
565        // --- BlockDiagonal: non-zero blocks along diagonal ---
566        if is_square && rows >= 4 {
567            if Self::is_block_diagonal(rows, data, TOL) {
568                patterns.push(MatrixPattern::BlockDiagonal);
569            }
570        }
571
572        // --- Toeplitz: each diagonal has constant value ---
573        if rows > 1 && cols > 1 {
574            let mut is_toeplitz = true;
575            // Check each diagonal
576            for d in -(rows as isize - 1)..(cols as isize) {
577                // Get the first value on this diagonal
578                let first = if d >= 0 {
579                    at(0, d as usize)
580                } else {
581                    at((-d) as usize, 0)
582                };
583                // Check all elements on this diagonal
584                let start_i = if d >= 0 { 0 } else { (-d) as usize };
585                let start_j = if d >= 0 { d as usize } else { 0 };
586                let mut i = start_i;
587                let mut j = start_j;
588                while i < rows && j < cols {
589                    if (at(i, j) - first).abs() > TOL {
590                        is_toeplitz = false;
591                        break;
592                    }
593                    i += 1;
594                    j += 1;
595                }
596                if !is_toeplitz {
597                    break;
598                }
599            }
600            if is_toeplitz {
601                patterns.push(MatrixPattern::Toeplitz);
602            }
603        }
604
605        // --- Orthogonal: A * A^T ≈ I ---
606        if is_square && rows > 0 {
607            if Self::is_orthogonal(rows, data, TOL) {
608                patterns.push(MatrixPattern::Orthogonal);
609            }
610        }
611
612        // --- Circulant: each row is a cyclic shift of the previous ---
613        if is_square && rows > 1 {
614            let mut is_circulant = true;
615            for i in 1..rows {
616                // Row i should be row (i-1) shifted right by 1 (cyclically)
617                for j in 0..cols {
618                    let expected = at(i - 1, if j == 0 { cols - 1 } else { j - 1 });
619                    if (at(i, j) - expected).abs() > TOL {
620                        is_circulant = false;
621                        break;
622                    }
623                }
624                if !is_circulant {
625                    break;
626                }
627            }
628            if is_circulant {
629                patterns.push(MatrixPattern::Circulant);
630            }
631        }
632
633        // --- Hankel: constant along anti-diagonals ---
634        if rows > 1 && cols > 1 {
635            let mut is_hankel = true;
636            // Anti-diagonal d ranges from 0 to (rows-1)+(cols-1)
637            // Element (i, j) is on anti-diagonal i + j
638            for d in 0..(rows + cols - 1) {
639                // Get first element on this anti-diagonal
640                let mut first_val: Option<f64> = None;
641                for i in 0..rows {
642                    let j = d as isize - i as isize;
643                    if j >= 0 && (j as usize) < cols {
644                        let v = at(i, j as usize);
645                        if first_val.is_none() {
646                            first_val = Some(v);
647                        } else if (v - first_val.unwrap()).abs() > TOL {
648                            is_hankel = false;
649                            break;
650                        }
651                    }
652                }
653                if !is_hankel {
654                    break;
655                }
656            }
657            if is_hankel {
658                patterns.push(MatrixPattern::Hankel);
659            }
660        }
661
662        // Always include Dense if no other pattern was detected
663        if patterns.is_empty() {
664            patterns.push(MatrixPattern::Dense);
665        }
666
667        patterns
668    }
669
670    /// Check if a square matrix is positive definite using Sylvester's criterion:
671    /// all leading principal minors must be positive.
672    fn is_positive_definite(n: usize, data: &[f64], tol: f64) -> bool {
673        for k in 1..=n {
674            // Compute the determinant of the k×k leading principal submatrix
675            let mut sub = vec![0.0; k * k];
676            for i in 0..k {
677                for j in 0..k {
678                    sub[i * k + j] = data[i * n + j];
679                }
680            }
681            // Compute determinant via LU-like recursive expansion for small k
682            let det = Self::determinant(k, &sub);
683            if det <= tol {
684                return false;
685            }
686        }
687        true
688    }
689
690    /// Compute the determinant of an n×n matrix via LU decomposition
691    fn determinant(n: usize, data: &[f64]) -> f64 {
692        if n == 0 {
693            return 1.0;
694        }
695        if n == 1 {
696            return data[0];
697        }
698        // LU decomposition with partial pivoting
699        let mut a = data.to_vec();
700        let mut sign = 1.0_f64;
701        for i in 0..n {
702            // Find pivot
703            let mut max_row = i;
704            let mut max_val = a[i * n + i].abs();
705            for k in (i + 1)..n {
706                if a[k * n + i].abs() > max_val {
707                    max_val = a[k * n + i].abs();
708                    max_row = k;
709                }
710            }
711            if max_val < 1e-15 {
712                return 0.0; // singular
713            }
714            if max_row != i {
715                for j in 0..n {
716                    let tmp = a[i * n + j];
717                    a[i * n + j] = a[max_row * n + j];
718                    a[max_row * n + j] = tmp;
719                }
720                sign = -sign;
721            }
722            // Eliminate
723            for k in (i + 1)..n {
724                let factor = a[k * n + i] / a[i * n + i];
725                for j in i..n {
726                    a[k * n + j] -= factor * a[i * n + j];
727                }
728            }
729        }
730        let mut det = sign;
731        for i in 0..n {
732            det *= a[i * n + i];
733        }
734        det
735    }
736
737    /// Check if a square matrix is block diagonal (non-zero blocks along the diagonal)
738    fn is_block_diagonal(n: usize, data: &[f64], tol: f64) -> bool {
739        // Heuristic: check if there's a consistent block size where off-block
740        // elements are zero. Try block sizes 2, 4, etc.
741        let at = |i: usize, j: usize| -> f64 { data[i * n + j] };
742        for block_size in [2, 4, 8].iter() {
743            if *block_size >= n {
744                continue;
745            }
746            if n % block_size != 0 {
747                continue;
748            }
749            let mut is_block_diag = true;
750            'outer: for bi in 0..(n / block_size) {
751                for bj in 0..(n / block_size) {
752                    if bi == bj {
753                        continue; // diagonal block
754                    }
755                    // Check off-diagonal block is all zeros
756                    for i in 0..*block_size {
757                        for j in 0..*block_size {
758                            if at(bi * block_size + i, bj * block_size + j).abs() > tol {
759                                is_block_diag = false;
760                                break 'outer;
761                            }
762                        }
763                    }
764                }
765            }
766            if is_block_diag {
767                return true;
768            }
769        }
770        false
771    }
772
773    /// Check if a square matrix is orthogonal: A * A^T ≈ I
774    fn is_orthogonal(n: usize, data: &[f64], tol: f64) -> bool {
775        let at = |i: usize, j: usize| -> f64 { data[i * n + j] };
776        // Compute A * A^T and check if it's approximately I
777        for i in 0..n {
778            for j in 0..n {
779                let mut dot = 0.0;
780                for k in 0..n {
781                    dot += at(i, k) * at(j, k);
782                }
783                let expected = if i == j { 1.0 } else { 0.0 };
784                if (dot - expected).abs() > tol * 10.0 {
785                    return false;
786                }
787            }
788        }
789        true
790    }
791}
792
793impl PatternRecognition {
794    /// Creates the registry with an empty `recognized_patterns` list, actively
795    /// populated during matrix analysis to record detected structural patterns.
796    pub fn new() -> Self {
797        Self {
798            recognized_patterns: Vec::new(),
799            pattern_library: PatternLibrary::new(),
800        }
801    }
802
803    /// Initializes the pattern library (populates pattern/hint maps).
804    pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
805        self.pattern_library.initialize()?;
806        Ok(())
807    }
808}
809
810impl PatternLibrary {
811    /// Creates an empty library; `initialize` populates the pattern names and
812    /// per-pattern optimization hints.
813    pub fn new() -> Self {
814        Self {
815            patterns: HashMap::new(),
816            optimization_hints: HashMap::new(),
817        }
818    }
819
820    /// Populates the `patterns` name map and `optimization_hints` entries for
821    /// every `MatrixPattern` variant.
822    pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
823        // Populate the patterns HashMap with names for each MatrixPattern variant
824        self.patterns
825            .insert("diagonal".to_string(), MatrixPattern::Diagonal);
826        self.patterns
827            .insert("triangular".to_string(), MatrixPattern::Triangular);
828        self.patterns
829            .insert("banded".to_string(), MatrixPattern::Banded);
830        self.patterns
831            .insert("symmetric".to_string(), MatrixPattern::Symmetric);
832        self.patterns.insert(
833            "positive_definite".to_string(),
834            MatrixPattern::PositiveDefinite,
835        );
836        self.patterns
837            .insert("orthogonal".to_string(), MatrixPattern::Orthogonal);
838        self.patterns
839            .insert("sparse".to_string(), MatrixPattern::Sparse);
840        self.patterns
841            .insert("dense".to_string(), MatrixPattern::Dense);
842        self.patterns
843            .insert("block_diagonal".to_string(), MatrixPattern::BlockDiagonal);
844        self.patterns
845            .insert("toeplitz".to_string(), MatrixPattern::Toeplitz);
846        self.patterns
847            .insert("hankel".to_string(), MatrixPattern::Hankel);
848        self.patterns
849            .insert("circulant".to_string(), MatrixPattern::Circulant);
850
851        // Populate optimization_hints with recommended algorithms for each pattern
852        self.optimization_hints.insert(
853            MatrixPattern::Diagonal,
854            OptimizationHint {
855                preferred_algorithm: "diagonal_scale".to_string(),
856                memory_layout: StorageFormat::CompressedSparseRow,
857                parallelization_strategy: "element_wise".to_string(),
858                vectorization_hints: vec!["scalar_multiply".to_string()],
859                estimated_speedup: 10.0,
860            },
861        );
862        self.optimization_hints.insert(
863            MatrixPattern::Triangular,
864            OptimizationHint {
865                preferred_algorithm: "triangular_solve".to_string(),
866                memory_layout: StorageFormat::RowMajor,
867                parallelization_strategy: "row_parallel".to_string(),
868                vectorization_hints: vec!["forward_substitution".to_string()],
869                estimated_speedup: 3.0,
870            },
871        );
872        self.optimization_hints.insert(
873            MatrixPattern::Banded,
874            OptimizationHint {
875                preferred_algorithm: "banded_gemm".to_string(),
876                memory_layout: StorageFormat::Blocked,
877                parallelization_strategy: "band_parallel".to_string(),
878                vectorization_hints: vec!["band_vectorization".to_string()],
879                estimated_speedup: 5.0,
880            },
881        );
882        self.optimization_hints.insert(
883            MatrixPattern::Symmetric,
884            OptimizationHint {
885                preferred_algorithm: "symmetric_gemm".to_string(),
886                memory_layout: StorageFormat::RowMajor,
887                parallelization_strategy: "block_parallel".to_string(),
888                vectorization_hints: vec!["symmetric_pack".to_string()],
889                estimated_speedup: 2.0,
890            },
891        );
892        self.optimization_hints.insert(
893            MatrixPattern::PositiveDefinite,
894            OptimizationHint {
895                preferred_algorithm: "cholesky_decomposition".to_string(),
896                memory_layout: StorageFormat::RowMajor,
897                parallelization_strategy: "block_parallel".to_string(),
898                vectorization_hints: vec!["cholesky_vectorized".to_string()],
899                estimated_speedup: 4.0,
900            },
901        );
902        self.optimization_hints.insert(
903            MatrixPattern::Orthogonal,
904            OptimizationHint {
905                preferred_algorithm: "orthogonal_transform".to_string(),
906                memory_layout: StorageFormat::RowMajor,
907                parallelization_strategy: "column_parallel".to_string(),
908                vectorization_hints: vec!["transpose_free".to_string()],
909                estimated_speedup: 3.0,
910            },
911        );
912        self.optimization_hints.insert(
913            MatrixPattern::Sparse,
914            OptimizationHint {
915                preferred_algorithm: "sparse_gemm".to_string(),
916                memory_layout: StorageFormat::CompressedSparseRow,
917                parallelization_strategy: "row_parallel".to_string(),
918                vectorization_hints: vec!["sparse_vectorization".to_string()],
919                estimated_speedup: 8.0,
920            },
921        );
922        self.optimization_hints.insert(
923            MatrixPattern::Dense,
924            OptimizationHint {
925                preferred_algorithm: "blocked_gemm".to_string(),
926                memory_layout: StorageFormat::Blocked,
927                parallelization_strategy: "block_parallel".to_string(),
928                vectorization_hints: vec!["avx2_vectorization".to_string()],
929                estimated_speedup: 1.0,
930            },
931        );
932        self.optimization_hints.insert(
933            MatrixPattern::BlockDiagonal,
934            OptimizationHint {
935                preferred_algorithm: "block_diagonal_gemm".to_string(),
936                memory_layout: StorageFormat::Blocked,
937                parallelization_strategy: "block_parallel".to_string(),
938                vectorization_hints: vec!["block_vectorization".to_string()],
939                estimated_speedup: 6.0,
940            },
941        );
942        self.optimization_hints.insert(
943            MatrixPattern::Toeplitz,
944            OptimizationHint {
945                preferred_algorithm: "toeplitz_fft".to_string(),
946                memory_layout: StorageFormat::RowMajor,
947                parallelization_strategy: "diagonal_parallel".to_string(),
948                vectorization_hints: vec!["fft_convolution".to_string()],
949                estimated_speedup: 7.0,
950            },
951        );
952        self.optimization_hints.insert(
953            MatrixPattern::Hankel,
954            OptimizationHint {
955                preferred_algorithm: "hankel_fft".to_string(),
956                memory_layout: StorageFormat::RowMajor,
957                parallelization_strategy: "anti_diagonal_parallel".to_string(),
958                vectorization_hints: vec!["fft_convolution".to_string()],
959                estimated_speedup: 7.0,
960            },
961        );
962        self.optimization_hints.insert(
963            MatrixPattern::Circulant,
964            OptimizationHint {
965                preferred_algorithm: "circulant_fft".to_string(),
966                memory_layout: StorageFormat::RowMajor,
967                parallelization_strategy: "row_parallel".to_string(),
968                vectorization_hints: vec!["fft_convolution".to_string()],
969                estimated_speedup: 8.0,
970            },
971        );
972
973        Ok(())
974    }
975
976    /// Return the optimization hint for a given pattern
977    pub fn get_optimization_hint(&self, pattern: &MatrixPattern) -> Option<&OptimizationHint> {
978        self.optimization_hints.get(pattern)
979    }
980}
981
982impl MatrixTransformer {
983    /// Registers the four rule variants and an empty history. NOTE:
984    /// `transformation_rules`/`transformation_history` are inert registries —
985    /// the real work happens in `transform_matrix`/`optimize_layout`.
986    pub fn new() -> Self {
987        Self {
988            transformation_rules: vec![
989                TransformationRule::LayoutConversion,
990                TransformationRule::RowColumnSwap,
991                TransformationRule::BlockReordering,
992                TransformationRule::DataTypeConversion,
993            ],
994            transformation_history: Vec::new(),
995        }
996    }
997
998    /// No-op — the transformer has no preparable state.
999    pub fn initialize(&mut self) -> Result<(), LinearAlgebraError> {
1000        Ok(())
1001    }
1002
1003    /// Transform a matrix's in-memory storage layout to `target_layout`.
1004    ///
1005    /// The source layout is inferred from `matrix.storage_format`. The
1006    /// returned matrix has its `data` buffer reorganised and its
1007    /// `storage_format` (and `metadata.storage_format`) updated to reflect
1008    /// the new layout. Row/column dimensions and element values are preserved.
1009    ///
1010    /// Supported conversions:
1011    /// - `RowMajor` <-> `ColMajor` (transpose storage layout)
1012    /// - `Blocked(inner, block_size)` (reorganise into cache-friendly tiles)
1013    /// - `Packed` (pad each row to a multiple of the SIMD vector width)
1014    ///
1015    /// Reading from a `Blocked` source is not supported because the block size
1016    /// is not carried in `Matrix` metadata; reading from sparse formats
1017    /// (`CompressedSparseRow` / `CompressedSparseColumn`) is likewise
1018    /// unsupported. Both return an `OptimizationError`.
1019    pub fn transform_matrix(
1020        &self,
1021        matrix: &Matrix,
1022        target_layout: MatrixLayout,
1023    ) -> Result<Matrix, LinearAlgebraError> {
1024        let rows = matrix.rows;
1025        let cols = matrix.cols;
1026
1027        // Validate the source buffer is consistent with its declared layout.
1028        validate_source_buffer(matrix)?;
1029
1030        // Read a logical element (i, j) from the source according to its
1031        // current storage_format.
1032        let src =
1033            |i: usize, j: usize| -> Result<f64, LinearAlgebraError> { read_element(matrix, i, j) };
1034
1035        let (data, storage_format) = match target_layout {
1036            MatrixLayout::RowMajor => {
1037                let mut data = Vec::with_capacity(rows * cols);
1038                for i in 0..rows {
1039                    for j in 0..cols {
1040                        data.push(src(i, j)?);
1041                    }
1042                }
1043                (data, StorageFormat::RowMajor)
1044            }
1045            MatrixLayout::ColMajor => {
1046                let mut data = Vec::with_capacity(rows * cols);
1047                // Column-major: contiguous down each column.
1048                for j in 0..cols {
1049                    for i in 0..rows {
1050                        data.push(src(i, j)?);
1051                    }
1052                }
1053                (data, StorageFormat::ColumnMajor)
1054            }
1055            MatrixLayout::Blocked(inner, block_size) => {
1056                if block_size == 0 {
1057                    return Err(LinearAlgebraError::OptimizationError(
1058                        "Blocked layout requires block_size > 0".to_string(),
1059                    ));
1060                }
1061                let mut data = Vec::with_capacity(rows * cols);
1062                let block_rows = (rows + block_size - 1) / block_size;
1063                let block_cols = (cols + block_size - 1) / block_size;
1064                // Within-block element order follows the inner layout; default
1065                // to row-major for any non-column-major inner layout.
1066                let col_major_inner = *inner == MatrixLayout::ColMajor;
1067                for bi in 0..block_rows {
1068                    for bj in 0..block_cols {
1069                        let i_start = bi * block_size;
1070                        let i_end = rows.min((bi + 1) * block_size);
1071                        let j_start = bj * block_size;
1072                        let j_end = cols.min((bj + 1) * block_size);
1073                        if col_major_inner {
1074                            for j in j_start..j_end {
1075                                for i in i_start..i_end {
1076                                    data.push(src(i, j)?);
1077                                }
1078                            }
1079                        } else {
1080                            for i in i_start..i_end {
1081                                for j in j_start..j_end {
1082                                    data.push(src(i, j)?);
1083                                }
1084                            }
1085                        }
1086                    }
1087                }
1088                (data, StorageFormat::Blocked)
1089            }
1090            MatrixLayout::Packed => {
1091                let stride = padded_stride(cols);
1092                let mut data = vec![0.0; rows * stride];
1093                for i in 0..rows {
1094                    for j in 0..cols {
1095                        data[i * stride + j] = src(i, j)?;
1096                    }
1097                }
1098                (data, StorageFormat::Packed)
1099            }
1100        };
1101
1102        let mut result = matrix.clone();
1103        result.data = data;
1104        result.storage_format = storage_format.clone();
1105        result.metadata.storage_format = storage_format;
1106        Ok(result)
1107    }
1108
1109    /// Analyse an access pattern and automatically pick the best layout for
1110    /// the given matrix, then transform it.
1111    ///
1112    /// Layout selection heuristic:
1113    /// - [`AccessPattern::Sequential`] (row-wise traversal) -> `RowMajor`
1114    /// - [`AccessPattern::Strided`] (column-wise traversal) -> `ColMajor`
1115    /// - [`AccessPattern::Blocked`] -> `Blocked(RowMajor, block_size)` where
1116    ///   `block_size` is a cache-friendly tile (capped at 16)
1117    /// - [`AccessPattern::Random`] -> `RowMajor` (no clear winner; keep the
1118    ///   canonical layout)
1119    /// - [`AccessPattern::Adaptive`] -> `ColMajor` for tall matrices
1120    ///   (`rows > cols`), `RowMajor` otherwise
1121    pub fn optimize_layout(
1122        &self,
1123        matrix: &Matrix,
1124        access_pattern: &AccessPattern,
1125    ) -> Result<Matrix, LinearAlgebraError> {
1126        let target = match access_pattern {
1127            AccessPattern::Sequential => MatrixLayout::RowMajor,
1128            AccessPattern::Strided => MatrixLayout::ColMajor,
1129            AccessPattern::Blocked => {
1130                // Pick a cache-friendly tile size bounded by the matrix's
1131                // smaller dimension and a 16-element cap.
1132                let block_size = matrix.rows.min(matrix.cols).max(1).min(16);
1133                MatrixLayout::Blocked(Box::new(MatrixLayout::RowMajor), block_size)
1134            }
1135            AccessPattern::Random => MatrixLayout::RowMajor,
1136            AccessPattern::Adaptive => {
1137                if matrix.rows > matrix.cols {
1138                    MatrixLayout::ColMajor
1139                } else {
1140                    MatrixLayout::RowMajor
1141                }
1142            }
1143        };
1144        self.transform_matrix(matrix, target)
1145    }
1146}
1147
1148/// Padded row stride for the [`MatrixLayout::Packed`] layout: the column count
1149/// rounded up to the next multiple of [`SIMD_WIDTH`].
1150fn padded_stride(cols: usize) -> usize {
1151    ((cols + SIMD_WIDTH - 1) / SIMD_WIDTH) * SIMD_WIDTH
1152}
1153
1154/// Read logical element `(i, j)` from `matrix` according to its
1155/// `storage_format`. Returns an error for unsupported source layouts
1156/// (`Blocked`, sparse formats) or out-of-bounds indices.
1157fn read_element(matrix: &Matrix, i: usize, j: usize) -> Result<f64, LinearAlgebraError> {
1158    let rows = matrix.rows;
1159    let cols = matrix.cols;
1160    if i >= rows || j >= cols {
1161        return Err(LinearAlgebraError::OptimizationError(format!(
1162            "element index ({}, {}) out of bounds for matrix of shape {}x{}",
1163            i, j, rows, cols
1164        )));
1165    }
1166    let idx = match matrix.storage_format {
1167        StorageFormat::RowMajor => i * cols + j,
1168        StorageFormat::ColumnMajor => j * rows + i,
1169        StorageFormat::Packed => {
1170            let stride = padded_stride(cols);
1171            i * stride + j
1172        }
1173        StorageFormat::Blocked => {
1174            return Err(LinearAlgebraError::OptimizationError(
1175                "cannot read from Blocked source: block size is not stored in Matrix metadata"
1176                    .to_string(),
1177            ));
1178        }
1179        StorageFormat::CompressedSparseRow | StorageFormat::CompressedSparseColumn => {
1180            return Err(LinearAlgebraError::OptimizationError(
1181                "sparse source layouts are not supported by the layout transformer".to_string(),
1182            ));
1183        }
1184    };
1185    if idx >= matrix.data.len() {
1186        return Err(LinearAlgebraError::OptimizationError(format!(
1187            "linear index {} out of bounds for data buffer of length {} (layout {:?})",
1188            idx,
1189            matrix.data.len(),
1190            matrix.storage_format
1191        )));
1192    }
1193    Ok(matrix.data[idx])
1194}
1195
1196/// Validate that the source matrix's `data` buffer length is consistent with
1197/// its declared `storage_format` and dimensions.
1198fn validate_source_buffer(matrix: &Matrix) -> Result<(), LinearAlgebraError> {
1199    let expected = match matrix.storage_format {
1200        StorageFormat::RowMajor | StorageFormat::ColumnMajor | StorageFormat::Blocked => {
1201            matrix.rows * matrix.cols
1202        }
1203        StorageFormat::Packed => matrix.rows * padded_stride(matrix.cols),
1204        StorageFormat::CompressedSparseRow | StorageFormat::CompressedSparseColumn => {
1205            // Sparse formats carry their own structure; skip strict length
1206            // validation rather than guess the expected buffer size.
1207            return Ok(());
1208        }
1209    };
1210    if matrix.data.len() != expected {
1211        return Err(LinearAlgebraError::OptimizationError(format!(
1212            "source data length {} does not match expected {} for {:?} layout ({}x{})",
1213            matrix.data.len(),
1214            expected,
1215            matrix.storage_format,
1216            matrix.rows,
1217            matrix.cols
1218        )));
1219    }
1220    Ok(())
1221}
1222
1223#[derive(Debug, Clone)]
1224pub struct MatrixAnalysis {
1225    pub matrix_id: String,
1226    pub sparsity: f64,
1227    pub structure: MatrixPattern,
1228    /// All detected structural patterns
1229    pub detected_patterns: Vec<MatrixPattern>,
1230    pub access_pattern: AccessPattern,
1231    pub optimization_hints: Vec<String>,
1232    /// Recommended algorithms derived from optimization hints
1233    pub recommended_algorithms: Vec<String>,
1234}
1235
1236/// Result of a full matrix analysis (alias for MatrixAnalysis for API clarity)
1237pub type MatrixAnalysisResult = MatrixAnalysis;
1238
1239#[cfg(test)]
1240mod tests {
1241    use super::*;
1242
1243    fn make_matrix(id: &str, rows: usize, cols: usize, data: Vec<f64>) -> Matrix {
1244        let metadata = MatrixMetadata {
1245            matrix_id: id.to_string(),
1246            rows,
1247            cols,
1248            data_type: DataType::Float64,
1249            storage_format: StorageFormat::RowMajor,
1250            compression: CompressionType::None,
1251            created_at: 0,
1252            last_accessed: 0,
1253            access_count: 0,
1254        };
1255        Matrix {
1256            matrix_id: id.to_string(),
1257            rows,
1258            cols,
1259            data_type: DataType::Float64,
1260            data,
1261            storage_format: StorageFormat::RowMajor,
1262            metadata,
1263        }
1264    }
1265
1266    fn make_analyzer() -> MatrixAnalyzer {
1267        let mut analyzer = MatrixAnalyzer::new();
1268        analyzer.initialize().unwrap();
1269        analyzer
1270    }
1271
1272    #[test]
1273    fn test_detect_diagonal() {
1274        let analyzer = make_analyzer();
1275        // Diagonal matrix
1276        let m = make_matrix("d", 3, 3, vec![1.0, 0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 3.0]);
1277        let patterns = analyzer.detect_structure(&m);
1278        assert!(patterns.contains(&MatrixPattern::Diagonal));
1279    }
1280
1281    #[test]
1282    fn test_detect_upper_triangular() {
1283        let analyzer = make_analyzer();
1284        let m = make_matrix("u", 3, 3, vec![1.0, 2.0, 3.0, 0.0, 4.0, 5.0, 0.0, 0.0, 6.0]);
1285        let patterns = analyzer.detect_structure(&m);
1286        assert!(patterns.contains(&MatrixPattern::Triangular));
1287    }
1288
1289    #[test]
1290    fn test_detect_lower_triangular() {
1291        let analyzer = make_analyzer();
1292        let m = make_matrix("l", 3, 3, vec![1.0, 0.0, 0.0, 2.0, 3.0, 0.0, 4.0, 5.0, 6.0]);
1293        let patterns = analyzer.detect_structure(&m);
1294        assert!(patterns.contains(&MatrixPattern::Triangular));
1295    }
1296
1297    #[test]
1298    fn test_detect_symmetric() {
1299        let analyzer = make_analyzer();
1300        let m = make_matrix("s", 3, 3, vec![1.0, 2.0, 3.0, 2.0, 4.0, 5.0, 3.0, 5.0, 6.0]);
1301        let patterns = analyzer.detect_structure(&m);
1302        assert!(patterns.contains(&MatrixPattern::Symmetric));
1303    }
1304
1305    #[test]
1306    fn test_detect_not_symmetric() {
1307        let analyzer = make_analyzer();
1308        let m = make_matrix("ns", 2, 2, vec![1.0, 2.0, 3.0, 4.0]);
1309        let patterns = analyzer.detect_structure(&m);
1310        assert!(!patterns.contains(&MatrixPattern::Symmetric));
1311    }
1312
1313    #[test]
1314    fn test_detect_positive_definite() {
1315        let analyzer = make_analyzer();
1316        // [[2,1],[1,2]] is symmetric positive definite (eigenvalues 1, 3)
1317        let m = make_matrix("pd", 2, 2, vec![2.0, 1.0, 1.0, 2.0]);
1318        let patterns = analyzer.detect_structure(&m);
1319        assert!(patterns.contains(&MatrixPattern::PositiveDefinite));
1320    }
1321
1322    #[test]
1323    fn test_detect_not_positive_definite() {
1324        let analyzer = make_analyzer();
1325        // [[1,2],[2,1]] is symmetric but not positive definite (eigenvalues -1, 3)
1326        let m = make_matrix("npd", 2, 2, vec![1.0, 2.0, 2.0, 1.0]);
1327        let patterns = analyzer.detect_structure(&m);
1328        assert!(!patterns.contains(&MatrixPattern::PositiveDefinite));
1329    }
1330
1331    #[test]
1332    fn test_detect_sparse() {
1333        let analyzer = make_analyzer();
1334        // 4x4 matrix with mostly zeros
1335        let m = make_matrix(
1336            "sp",
1337            4,
1338            4,
1339            vec![
1340                1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0,
1341            ],
1342        );
1343        let patterns = analyzer.detect_structure(&m);
1344        assert!(patterns.contains(&MatrixPattern::Sparse));
1345    }
1346
1347    #[test]
1348    fn test_detect_dense() {
1349        let analyzer = make_analyzer();
1350        let m = make_matrix("d", 2, 2, vec![1.0, 2.0, 3.0, 4.0]);
1351        let patterns = analyzer.detect_structure(&m);
1352        assert!(patterns.contains(&MatrixPattern::Dense));
1353    }
1354
1355    #[test]
1356    fn test_detect_banded() {
1357        let analyzer = make_analyzer();
1358        // Tridiagonal 5x5 (bandwidth 1, which is < 5/3 = 1.66)
1359        let m = make_matrix(
1360            "b",
1361            5,
1362            5,
1363            vec![
1364                1.0, 2.0, 0.0, 0.0, 0.0, 3.0, 4.0, 5.0, 0.0, 0.0, 0.0, 6.0, 7.0, 8.0, 0.0, 0.0,
1365                0.0, 9.0, 10.0, 11.0, 0.0, 0.0, 0.0, 12.0, 13.0,
1366            ],
1367        );
1368        let patterns = analyzer.detect_structure(&m);
1369        assert!(patterns.contains(&MatrixPattern::Banded));
1370    }
1371
1372    #[test]
1373    fn test_detect_toeplitz() {
1374        let analyzer = make_analyzer();
1375        // Toeplitz: each diagonal constant
1376        // [[1,2,3],[4,1,2],[5,4,1]]
1377        let m = make_matrix("t", 3, 3, vec![1.0, 2.0, 3.0, 4.0, 1.0, 2.0, 5.0, 4.0, 1.0]);
1378        let patterns = analyzer.detect_structure(&m);
1379        assert!(patterns.contains(&MatrixPattern::Toeplitz));
1380    }
1381
1382    #[test]
1383    fn test_detect_orthogonal() {
1384        let analyzer = make_analyzer();
1385        // 2x2 rotation matrix (orthogonal)
1386        // [[0, -1], [1, 0]] — A*A^T = I
1387        let m = make_matrix("o", 2, 2, vec![0.0, -1.0, 1.0, 0.0]);
1388        let patterns = analyzer.detect_structure(&m);
1389        assert!(patterns.contains(&MatrixPattern::Orthogonal));
1390    }
1391
1392    #[test]
1393    fn test_detect_circulant() {
1394        let analyzer = make_analyzer();
1395        // Circulant 3x3: each row is cyclic shift of previous
1396        // [[1,2,3],[3,1,2],[2,3,1]]
1397        let m = make_matrix("c", 3, 3, vec![1.0, 2.0, 3.0, 3.0, 1.0, 2.0, 2.0, 3.0, 1.0]);
1398        let patterns = analyzer.detect_structure(&m);
1399        assert!(patterns.contains(&MatrixPattern::Circulant));
1400    }
1401
1402    #[test]
1403    fn test_detect_hankel() {
1404        let analyzer = make_analyzer();
1405        // Hankel: constant along anti-diagonals
1406        // [[1,2,3],[2,3,4],[3,4,5]]
1407        let m = make_matrix("h", 3, 3, vec![1.0, 2.0, 3.0, 2.0, 3.0, 4.0, 3.0, 4.0, 5.0]);
1408        let patterns = analyzer.detect_structure(&m);
1409        assert!(patterns.contains(&MatrixPattern::Hankel));
1410    }
1411
1412    #[test]
1413    fn test_detect_block_diagonal() {
1414        let analyzer = make_analyzer();
1415        // 4x4 block diagonal with 2x2 blocks
1416        let m = make_matrix(
1417            "bd",
1418            4,
1419            4,
1420            vec![
1421                1.0, 2.0, 0.0, 0.0, 3.0, 4.0, 0.0, 0.0, 0.0, 0.0, 5.0, 6.0, 0.0, 0.0, 7.0, 8.0,
1422            ],
1423        );
1424        let patterns = analyzer.detect_structure(&m);
1425        assert!(patterns.contains(&MatrixPattern::BlockDiagonal));
1426    }
1427
1428    #[test]
1429    fn test_pattern_library_initialize() {
1430        let mut lib = PatternLibrary::new();
1431        lib.initialize().unwrap();
1432
1433        // All 12 patterns should be registered
1434        assert_eq!(lib.patterns.len(), 12);
1435        assert_eq!(lib.optimization_hints.len(), 12);
1436    }
1437
1438    #[test]
1439    fn test_get_optimization_hint() {
1440        let mut lib = PatternLibrary::new();
1441        lib.initialize().unwrap();
1442
1443        let hint = lib.get_optimization_hint(&MatrixPattern::Diagonal);
1444        assert!(hint.is_some());
1445        let h = hint.unwrap();
1446        assert_eq!(h.preferred_algorithm, "diagonal_scale");
1447        assert!(h.estimated_speedup > 0.0);
1448
1449        let hint2 = lib.get_optimization_hint(&MatrixPattern::Sparse);
1450        assert!(hint2.is_some());
1451        assert_eq!(hint2.unwrap().preferred_algorithm, "sparse_gemm");
1452    }
1453
1454    #[test]
1455    fn test_analyze_matrix() {
1456        let mut analyzer = make_analyzer();
1457        let m = make_matrix("s", 2, 2, vec![2.0, 1.0, 1.0, 2.0]);
1458        let result = analyzer.analyze_matrix(&m).unwrap();
1459
1460        assert_eq!(result.matrix_id, "s");
1461        assert!(result.detected_patterns.contains(&MatrixPattern::Symmetric));
1462        assert!(result
1463            .detected_patterns
1464            .contains(&MatrixPattern::PositiveDefinite));
1465        assert!(!result.recommended_algorithms.is_empty());
1466    }
1467
1468    #[test]
1469    fn test_analyze_matrix_sparsity() {
1470        let mut analyzer = make_analyzer();
1471        // 3x3 with 5 zeros out of 9 → sparsity = 5/9
1472        let m = make_matrix(
1473            "sp",
1474            3,
1475            3,
1476            vec![1.0, 0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 3.0],
1477        );
1478        let result = analyzer.analyze_matrix(&m).unwrap();
1479        assert!((result.sparsity - 6.0 / 9.0).abs() < 1e-10); // 6 zeros, 3 non-zeros
1480    }
1481
1482    // ---- MatrixTransformer layout-conversion tests ----
1483
1484    fn make_transformer() -> MatrixTransformer {
1485        let mut t = MatrixTransformer::new();
1486        t.initialize().unwrap();
1487        t
1488    }
1489
1490    /// Build a column-major matrix from a row-major `data` description.
1491    /// `data` is given in row-major order (row by row); the returned matrix
1492    /// stores it in column-major order with `storage_format = ColumnMajor`.
1493    fn make_col_matrix(id: &str, rows: usize, cols: usize, row_major_data: Vec<f64>) -> Matrix {
1494        // Reorganise row-major input into column-major storage.
1495        let mut col_major = Vec::with_capacity(rows * cols);
1496        for j in 0..cols {
1497            for i in 0..rows {
1498                col_major.push(row_major_data[i * cols + j]);
1499            }
1500        }
1501        let metadata = MatrixMetadata {
1502            matrix_id: id.to_string(),
1503            rows,
1504            cols,
1505            data_type: DataType::Float64,
1506            storage_format: StorageFormat::ColumnMajor,
1507            compression: CompressionType::None,
1508            created_at: 0,
1509            last_accessed: 0,
1510            access_count: 0,
1511        };
1512        Matrix {
1513            matrix_id: id.to_string(),
1514            rows,
1515            cols,
1516            data_type: DataType::Float64,
1517            data: col_major,
1518            storage_format: StorageFormat::ColumnMajor,
1519            metadata,
1520        }
1521    }
1522
1523    /// Read element (i, j) from a blocked-layout matrix with a known block size
1524    /// (row-major within blocks, row-major block order). Used to verify the
1525    /// blocked transform reorganised the data correctly.
1526    fn read_blocked(m: &Matrix, block_size: usize, i: usize, j: usize) -> f64 {
1527        let rows = m.rows;
1528        let cols = m.cols;
1529        let block_rows = (rows + block_size - 1) / block_size;
1530        let block_cols = (cols + block_size - 1) / block_size;
1531        let bi = i / block_size;
1532        let bj = j / block_size;
1533        let li = i % block_size; // local row within block
1534        let lj = j % block_size; // local col within block
1535                                 // Count elements in blocks preceding (bi, bj) in row-major block order.
1536        let mut offset = 0usize;
1537        'outer: for bbi in 0..block_rows {
1538            for bbj in 0..block_cols {
1539                if bbi == bi && bbj == bj {
1540                    break 'outer;
1541                }
1542                let i_end = rows.min((bbi + 1) * block_size);
1543                let j_end = cols.min((bbj + 1) * block_size);
1544                offset += (i_end - bbi * block_size) * (j_end - bbj * block_size);
1545            }
1546        }
1547        // Local block dimensions for block (bi, bj).
1548        let i_start = bi * block_size;
1549        let j_start = bj * block_size;
1550        let _local_rows = rows.min((bi + 1) * block_size) - i_start;
1551        let local_cols = cols.min((bj + 1) * block_size) - j_start;
1552        // Row-major within block.
1553        offset += li * local_cols + lj;
1554        m.data[offset]
1555    }
1556
1557    #[test]
1558    fn test_row_to_col_major() {
1559        let transformer = make_transformer();
1560        // 2x3 matrix:
1561        //   [[1, 2, 3],
1562        //    [4, 5, 6]]
1563        let m = make_matrix("rm", 2, 3, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1564        assert_eq!(m.storage_format, StorageFormat::RowMajor);
1565
1566        let result = transformer
1567            .transform_matrix(&m, MatrixLayout::ColMajor)
1568            .unwrap();
1569
1570        assert_eq!(result.storage_format, StorageFormat::ColumnMajor);
1571        assert_eq!(result.metadata.storage_format, StorageFormat::ColumnMajor);
1572        assert_eq!(result.rows, 2);
1573        assert_eq!(result.cols, 3);
1574        // Column-major: column 0 = [1, 4], column 1 = [2, 5], column 2 = [3, 6]
1575        assert_eq!(result.data, vec![1.0, 4.0, 2.0, 5.0, 3.0, 6.0]);
1576        // Verify every logical element is preserved under col-major addressing.
1577        for i in 0..2 {
1578            for j in 0..3 {
1579                let expected = m.data[i * 3 + j];
1580                let got = result.data[j * 2 + i];
1581                assert_eq!(got, expected, "element ({},{}) mismatch", i, j);
1582            }
1583        }
1584    }
1585
1586    #[test]
1587    fn test_col_to_row_major() {
1588        let transformer = make_transformer();
1589        // Build a column-major matrix representing [[1,2,3],[4,5,6]].
1590        let m = make_col_matrix("cm", 2, 3, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1591        assert_eq!(m.storage_format, StorageFormat::ColumnMajor);
1592        assert_eq!(m.data, vec![1.0, 4.0, 2.0, 5.0, 3.0, 6.0]);
1593
1594        let result = transformer
1595            .transform_matrix(&m, MatrixLayout::RowMajor)
1596            .unwrap();
1597
1598        assert_eq!(result.storage_format, StorageFormat::RowMajor);
1599        assert_eq!(result.rows, 2);
1600        assert_eq!(result.cols, 3);
1601        // Row-major: [[1,2,3],[4,5,6]] flattened row by row.
1602        assert_eq!(result.data, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1603        // Verify every logical element is preserved under row-major addressing.
1604        for i in 0..2 {
1605            for j in 0..3 {
1606                let expected = m.data[j * 2 + i]; // col-major source read
1607                let got = result.data[i * 3 + j]; // row-major result read
1608                assert_eq!(got, expected, "element ({},{}) mismatch", i, j);
1609            }
1610        }
1611    }
1612
1613    #[test]
1614    fn test_blocked_layout() {
1615        let transformer = make_transformer();
1616        // 4x4 matrix 1..16 (row-major):
1617        //   [[ 1,  2,  3,  4],
1618        //    [ 5,  6,  7,  8],
1619        //    [ 9, 10, 11, 12],
1620        //    [13, 14, 15, 16]]
1621        let m = make_matrix(
1622            "blk",
1623            4,
1624            4,
1625            vec![
1626                1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0,
1627                16.0,
1628            ],
1629        );
1630
1631        let result = transformer
1632            .transform_matrix(
1633                &m,
1634                MatrixLayout::Blocked(Box::new(MatrixLayout::RowMajor), 2),
1635            )
1636            .unwrap();
1637
1638        assert_eq!(result.storage_format, StorageFormat::Blocked);
1639        assert_eq!(result.rows, 4);
1640        assert_eq!(result.cols, 4);
1641        assert_eq!(result.data.len(), 16);
1642        // Expected block order (2x2 blocks, row-major within each block):
1643        //   block(0,0) = [1, 2, 5, 6]
1644        //   block(0,1) = [3, 4, 7, 8]
1645        //   block(1,0) = [9, 10, 13, 14]
1646        //   block(1,1) = [11, 12, 15, 16]
1647        assert_eq!(
1648            result.data,
1649            vec![
1650                1.0, 2.0, 5.0, 6.0, 3.0, 4.0, 7.0, 8.0, 9.0, 10.0, 13.0, 14.0, 11.0, 12.0, 15.0,
1651                16.0,
1652            ]
1653        );
1654        // Verify every logical element is recoverable from the blocked buffer.
1655        for i in 0..4 {
1656            for j in 0..4 {
1657                let expected = m.data[i * 4 + j];
1658                let got = read_blocked(&result, 2, i, j);
1659                assert_eq!(got, expected, "blocked element ({},{}) mismatch", i, j);
1660            }
1661        }
1662    }
1663
1664    #[test]
1665    fn test_optimize_layout_row_access() {
1666        let transformer = make_transformer();
1667        let m = make_matrix("r", 2, 3, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1668        // Sequential access = row-heavy traversal -> RowMajor.
1669        let result = transformer
1670            .optimize_layout(&m, &AccessPattern::Sequential)
1671            .unwrap();
1672        assert_eq!(result.storage_format, StorageFormat::RowMajor);
1673        // Row-major data is unchanged from the row-major source.
1674        assert_eq!(result.data, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1675    }
1676
1677    #[test]
1678    fn test_optimize_layout_col_access() {
1679        let transformer = make_transformer();
1680        let m = make_matrix("c", 2, 3, vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
1681        // Strided access = column-heavy traversal -> ColMajor.
1682        let result = transformer
1683            .optimize_layout(&m, &AccessPattern::Strided)
1684            .unwrap();
1685        assert_eq!(result.storage_format, StorageFormat::ColumnMajor);
1686        // Column-major reorganisation: [1, 4, 2, 5, 3, 6].
1687        assert_eq!(result.data, vec![1.0, 4.0, 2.0, 5.0, 3.0, 6.0]);
1688    }
1689
1690    // === Strategy registry and PatternRecognition tests ===
1691
1692    #[test]
1693    fn test_pattern_recognition_accumulates_patterns() {
1694        let mut analyzer = make_analyzer();
1695        assert!(analyzer.pattern_recognition.recognized_patterns.is_empty());
1696
1697        // Analyze diagonal matrix
1698        let m_diag = make_matrix("d", 3, 3, vec![1.0, 0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 3.0]);
1699        analyzer.analyze_matrix(&m_diag).unwrap();
1700        assert!(analyzer
1701            .pattern_recognition
1702            .recognized_patterns
1703            .contains(&MatrixPattern::Diagonal));
1704
1705        // Analyze Toeplitz matrix
1706        let m_toep = make_matrix(
1707            "t",
1708            3,
1709            3,
1710            vec![1.0, 2.0, 3.0, 4.0, 1.0, 2.0, 5.0, 4.0, 1.0],
1711        );
1712        analyzer.analyze_matrix(&m_toep).unwrap();
1713        assert!(analyzer
1714            .pattern_recognition
1715            .recognized_patterns
1716            .contains(&MatrixPattern::Toeplitz));
1717    }
1718
1719    #[test]
1720    fn test_optimizer_strategy_registry_and_resolution() {
1721        let mut opt = MatrixOptimizer::new();
1722        assert!(opt.is_strategy_enabled(&OptimizationStrategy::AlgorithmSelection));
1723        assert!(opt.is_strategy_enabled(&OptimizationStrategy::Parallelization));
1724
1725        // Unregister Parallelization
1726        opt.unregister_strategy(&OptimizationStrategy::Parallelization);
1727        assert!(!opt.is_strategy_enabled(&OptimizationStrategy::Parallelization));
1728
1729        // Resolving Parallelization should fall back to CacheOptimization
1730        let fallbacks = [
1731            OptimizationStrategy::CacheOptimization,
1732            OptimizationStrategy::Vectorization,
1733        ];
1734        let chosen = opt
1735            .resolve_strategy(OptimizationStrategy::Parallelization, &fallbacks)
1736            .unwrap();
1737        assert_eq!(chosen, OptimizationStrategy::CacheOptimization);
1738
1739        // Register it back
1740        opt.register_strategy(OptimizationStrategy::Parallelization);
1741        assert!(opt.is_strategy_enabled(&OptimizationStrategy::Parallelization));
1742        let chosen2 = opt
1743            .resolve_strategy(OptimizationStrategy::Parallelization, &fallbacks)
1744            .unwrap();
1745        assert_eq!(chosen2, OptimizationStrategy::Parallelization);
1746    }
1747
1748    #[test]
1749    fn test_optimize_multiplication_consults_hints_and_strategies() {
1750        let mut engine = OptimizationEngine::new();
1751        engine.initialize().unwrap();
1752
1753        // 1. Diagonal matrix operand should trigger AlgorithmSelection with ~10.0x gain
1754        let m_diag = make_matrix("d", 3, 3, vec![2.0, 0.0, 0.0, 0.0, 3.0, 0.0, 0.0, 0.0, 4.0]);
1755        let m_dense = make_matrix("dn", 3, 3, vec![1.0; 9]);
1756
1757        let opt_mult = engine.optimize_multiplication(&m_diag, &m_dense).unwrap();
1758        assert_eq!(
1759            opt_mult.optimization_strategy,
1760            OptimizationStrategy::AlgorithmSelection
1761        );
1762        assert!(opt_mult.expected_performance_gain >= 10.0);
1763        assert_eq!(engine.optimizer.optimization_history.len(), 1);
1764
1765        // 2. If AlgorithmSelection is unregistered, optimizer should fall back to an enabled strategy
1766        engine
1767            .optimizer
1768            .unregister_strategy(&OptimizationStrategy::AlgorithmSelection);
1769        let opt_mult_fallback = engine.optimize_multiplication(&m_diag, &m_dense).unwrap();
1770        assert_ne!(
1771            opt_mult_fallback.optimization_strategy,
1772            OptimizationStrategy::AlgorithmSelection
1773        );
1774        assert!(engine
1775            .optimizer
1776            .is_strategy_enabled(&opt_mult_fallback.optimization_strategy));
1777    }
1778}